作者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/cn.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