作者woody3724 (woody)
看板Prob_Solve
标题[问题] LeetCode 378. Kth Smallest Element...
时间Thu Jun 15 23:59:20 2017
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就不行
谢谢
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 27.105.50.155
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Prob_Solve/M.1497542363.A.8D9.html
1F：推 FRAXIS: 应该可以写 if (count > k) hi = mid - 1 else lo = mid 06/16 07:56
2F：→ FRAXIS: 在 sorted matrix 找中位数的问题 以前在版上有讨论过 06/16 07:57
4F：推 JameC: 在第三行有个注解：[lo, hi)，如果hi = mid - 1，搜索的区 06/16 16:03
5F：→ JameC: 间就会变成[lo, hi]，这样会出问题。 06/16 16:03
6F：→ JameC: 可以仔细思考看看，他最後为什麽是return lo，如果搜索的区 06/16 16:05
7F：→ JameC: 间变成[lo, hi]，那最後会无法确定答案是哪一个。 06/16 16:06
8F：→ JameC: 在做二分搜的时候，通常都不会包含 06/16 16:07
9F：→ JameC: 终点，就是这个原因 06/16 16:08
10F：→ JameC: 这个题目我没有仔细地研究，只是聊聊我对二分搜的一些理解 06/16 16:09
11F：→ JameC: 有错还请不吝指正 06/16 16:10
感谢各位回覆，但我还是不太懂，到底甚麽时候 high = mid - 1，甚麽时候 high = mid
以及甚麽时候 return mid，甚麽时候 return low
再以这题做例子
http://tinyurl.com/y8nezn9x
用binary search的作法:
http://tinyurl.com/ya27ye8l
这里是 high = mid - 1，但我的这篇文章原始题目的high却是 high = mid
搞得我好乱啊........
自己实际代数字下去也归纳不出到底甚麽时候要high = mid 甚麽时候要 high = mid - 1
该 return mid 还是return low 我也一头雾水............
※ 编辑: woody3724 (150.117.206.13), 06/17/2017 23:55:43
12F：推 JameC: 嗯...其实我也不太懂他的写法，我自己写的话，while回圈内 06/18 11:55
13F：→ JameC: 只要三行就可以搞定，我晚点再来想想该怎麽解释比较好。 06/18 11:56
14F：→ pttworld: if有判断mid等於则high就是mid-1，因为mid已经不是了。 06/18 21:10