PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

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

看板Prob_Solve (計算數學 Problem Solving)作者powertodream (The Beginning)時間7年前 (2017/06/20 21:24)推噓0(0推 0噓 0→)

留言0則, 0人參與討論串2/3 (看更多)

※ 引述《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 -- 這世界最難以理解的事就是所有事情都是可以理解的 (愛因斯坦). -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 122.116.76.244 ※ 文章網址: https://www.ptt.cc/bbs/Prob_Solve/M.1497965051.A.8B0.html