[理工] 算法一题:2个sorted array找median

楼主: ff00662299 (goneboy)   2022-12-16 20:50:47
给两个sorted array A跟B,
A的长度是m,B的长度是n。
想问为什么要找这m+n个数的median的时间可以做到log min(m,n)?
作者: A4P8T6X9 (残废的名侦探)   2022-12-16 23:59:00
binary search 任一 array,每次取中点代表该 array要贡献多少个数字到合并后的阵列的左边,因为有两个阵列的长度,另外一个阵列要贡献多少个数字可以直接算出来,之后如果贡献出来的左边的值大于另外一半右边的值,代表这个切法错误,需要调整,基本上调整方式会根据刚刚贡献出来的左边数字进行调整。因为除了 binary search 以外都是常数时间,且可以任选一个 array 做,所以是 log(min(m, n))
作者: a93011abc (阿屎)   2022-12-20 20:27:00
设较长的阵列为m拿m[m+n/2]去跟n[i]比;i=0~n。若n较大结束n较小i+的同时m阵列往前一格 所以最多会走n个
作者: lingege321 (happyChicken)   2022-12-23 21:58:00
Leetcode第四题 可以查

Links booklink

Contact Us: admin [ a t ] ucptt.com