作者ff00662299 (Broken Coastline)
看板Grad-ProbAsk
標題[理工] 演算法一題:2個sorted array找median
時間Fri Dec 16 20:50:47 2022
給兩個sorted array A跟B，
A的長度是m，B的長度是n。
想問為什麼要找這m+n個數的median的時間可以做到log min(m,n)?
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.114.233.76 (臺灣)
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Grad-ProbAsk/M.1671195049.A.C69.html
1F：推 A4P8T6X9: binary search 任一 array，每次取中點代表該 array 12/16 23:59
謝謝A大！很完整的說明
2F：→ A4P8T6X9: 要貢獻多少個數字到合併後的陣列的左邊，因為有兩個陣 12/16 23:59
3F：→ A4P8T6X9: 列的長度，另外一個陣列要貢獻多少個數字可以直接算出 12/16 23:59
4F：→ A4P8T6X9: 來，之後如果貢獻出來的左邊的值大於另外一半右邊的值 12/16 23:59
5F：→ A4P8T6X9: ，代表這個切法錯誤，需要調整，基本上調整方式會根據 12/16 23:59
6F：→ A4P8T6X9: 剛剛貢獻出來的左邊數字進行調整。因為除了 binary sea 12/16 23:59
7F：→ A4P8T6X9: rch 以外都是常數時間，且可以任選一個 array 做，所以 12/16 23:59
8F：→ A4P8T6X9: 是 log(min(m, n)) 12/16 23:59
※ 編輯: ff00662299 (49.216.164.99 臺灣), 12/17/2022 22:50:46
9F：推 a93011abc: 設較長的陣列為m拿m[m+n/2]去跟n[i]比；i=0~n。若n較大 12/20 20:27
10F：→ a93011abc: 結束n較小i+的同時m陣列往前一格 所以最多會走n個 12/20 20:27
11F：→ lingege321: Leetcode第四題 可以查 12/23 21:58