PTT
Submit
Submit
选择语言
正體中文
简体中文
PTT
Grad-ProbAsk
[理工] 算法一题: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第四题 可以查
继续阅读
[商管] 资料处理
starQJ
[理工] 张凡计组上P.513
frank4133
[理工] 喻工数级数解
ciapa1015
[理工] [数学][核对] 111 台科大资工
qwerty2747
Re: [理工] 计系 107交大 第15题
ping990579
[理工] 109交大 计系 loop unrolling
ping990579
[理工] 工程机率
suspect1
[理工] 资结 调整max heap的算法问题
allenpong
[理工] 步阶函数 折积问题
pureblue1234
[理工] 104中央离散4
ping990579
Links
booklink
Contact Us: admin [ a t ] ucptt.com