求讲解 Median of Two Sorted Arrays 转换为 TopK 问题?

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

For Existing Member Sign In

• 请不要在回答技术问题时复制粘贴 AI 生成的内容

This topic created in 4002 days ago, the information mentioned may be changed or developed.

比较两个数组的中位数之后, 排除那部分蒙圈了

topk

median

arrays

3 replies • 2015-05-19 17:04:07 +08:00

deepreader

May 19, 2015

https://github.com/idf/LeetCode/blob/master/002%20Median%20of%20Two%20Sorted%20Arrays.py

看注释。

phx13ye

May 19, 2015

@deepreader
if A[m/2]>B[n/2] and k>m/2+n/2, then disregard B_left and B[n/2]
if A[m/2]>B[n/2] and k<=m/2+n/2, then disregard A_right and A[m/2]
if A[m/2]<=B[n/2] and k>m/2+n/2, then disregard A_left and A[m/2]
if A[m/2]<=B[n/2] and k<=m/2+n/2, then disregard B_right and B[n/2]
这里怎么理解

deepreader

May 19, 2015

@phx13ye 两个数组被分成四段，case 1的话，你要找的target则不可能在四段中值最小的那一段，其他的类推。