[理工] 演算法一題:2個sorted array找median

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