[問題] LeetCode 378. Kth Smallest Element...

[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就不行

謝謝


--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 27.105.50.155
※ 文章網址: https://www.ptt.cc/bbs/Prob_Solve/M.1497542363.A.8D9.html
推 FRAXIS: 應該可以寫 if (count > k) hi = mid - 1 else lo = mid
→ FRAXIS: 在 sorted matrix 找中位數的問題 以前在版上有討論過
→ FRAXIS: #1KF5PfAs
推 JameC: 在第三行有個註解：[lo, hi)，如果hi = mid - 1，搜索的區
→ JameC: 間就會變成[lo, hi]，這樣會出問題。
→ JameC: 可以仔細思考看看，他最後為什麼是return lo，如果搜索的區
→ JameC: 間變成[lo, hi]，那最後會無法確定答案是哪一個。
→ JameC: 在做二分搜的時候，通常都不會包含
→ JameC: 終點，就是這個原因
→ JameC: 這個題目我沒有仔細地研究，只是聊聊我對二分搜的一些理解
→ JameC: 有錯還請不吝指正
感謝各位回覆，但我還是不太懂，到底甚麼時候 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
推 JameC: 嗯...其實我也不太懂他的寫法，我自己寫的話，while迴圈內
→ JameC: 只要三行就可以搞定，我晚點再來想想該怎麼解釋比較好。
→ pttworld: if有判斷mid等於則high就是mid-1，因為mid已經不是了。