[問題] LeetCode 378. Kth Smallest Element...
看板Prob_Solve (計算數學 Problem Solving)作者woody3724 (woody)時間7年前 (2017/06/15 23:59)推噓3(3推 0噓 11→)留言14則, 3人參與討論串1/3 (看更多)
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
推
06/16 07:56, , 1F
06/16 07:56, 1F
→
06/16 07:57, , 2F
06/16 07:57, 2F
→
06/16 07:57, , 3F
06/16 07:57, 3F
推
06/16 16:03, , 4F
06/16 16:03, 4F
→
06/16 16:03, , 5F
06/16 16:03, 5F
→
06/16 16:05, , 6F
06/16 16:05, 6F
→
06/16 16:06, , 7F
06/16 16:06, 7F
→
06/16 16:07, , 8F
06/16 16:07, 8F
→
06/16 16:08, , 9F
06/16 16:08, 9F
→
06/16 16:09, , 10F
06/16 16:09, 10F
→
06/16 16:10, , 11F
06/16 16:10, 11F
感謝各位回覆，但我還是不太懂，到底甚麼時候 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
推
06/18 11:55, , 12F
06/18 11:55, 12F
→
06/18 11:56, , 13F
06/18 11:56, 13F
→
06/18 21:10, , 14F
06/18 21:10, 14F
討論串 (同標題文章)
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
