[问题] LeetCode 378. Kth Smallest Element...

楼主: woody3724 (woody)   2017-06-15 23:59:20
LeetCode 378. Kth Smallest Element in a Sorted Matrix
题目连结 http://tinyurl.com/y8sc949p
Given a n x n matrix where each of the rows and columns are sorted in
ascending order, find the kth smallest element in the matrix.
Note that it is the kth smallest element in the sorted order, not the kth
distinct element.
Example:
matrix = [[ 1, 5, 9],
[10,11,13],
[12,13,15]]
k = 8
return 13
目前正在研究用binary search解这题 http://tinyurl.com/ybqw4ubd
YUANGAO1023提到的Solution 2: Binary Search
大致的结构我都看懂了
但是不懂的是为什么是在while循环的最后
是else hi = mid; 而不是 else hi = mid - 1;
我有自己代数字实际跑一遍, else hi = mid; 是正确的,但是却不知道为什么这是正确
也不懂为什么 hi = mid - 1就不行
谢谢
作者: FRAXIS (喔喔)   2017-06-16 07:56:00
应该可以写 if (count > k) hi = mid - 1 else lo = mid在 sorted matrix 找中位数的问题 以前在版上有讨论过#1KF5PfAs
作者: JameC (智取其乳)   2017-06-16 16:03:00
在第三行有个注解:[lo, hi),如果hi = mid - 1,搜索的区间就会变成[lo, hi],这样会出问题。可以仔细思考看看,他最后为什么是return lo,如果搜索的区间变成[lo, hi],那最后会无法确定答案是哪一个。在做二分搜的时候,通常都不会包含终点,就是这个原因这个题目我没有仔细地研究,只是聊聊我对二分搜的一些理解有错还请不吝指正嗯...其实我也不太懂他的写法,我自己写的话,while循环内只要三行就可以搞定,我晚点再来想想该怎么解释比较好。
作者: pttworld (批踢踢世界)   2017-06-18 21:10:00
if有判断mid等于则high就是mid-1,因为mid已经不是了。

Links booklink

Contact Us: admin [ a t ] ucptt.com