※ 引述《woody3724 (woody)》之銘言：
: 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就不行
: 謝謝
他這個看起來是比較標準的寫法, 就是如果你有多個符合條件的element的話
他會return 第一個 符合這個條件的 element
之前我的習慣也是寫像是這樣
while (lo<=hi){
if (mid==target)
...
else if (mid > target)
hi = mid - 1;
else
lo = mid + 1;
};
不過這樣寫如果有多個符合條件的元素的話, 就會回傳隨機一個.
我理解上是這樣 可以再討論.
詳細可以看topcoder的這一篇, 不過我也沒有看完 只大概掃過而已, 有興趣可以詳讀
https://tinyurl.com/qcaj9aj