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

V2EX = way to explore

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

现在注册

已注册用户请登录

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

这是一个创建于 3514 天前的主题，其中的信息可能已经有所发展或是发生改变。

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

topk

median

arrays

3 条回复 • 2015-05-19 17:04:07 +08:00

deepreader

2015-05-19 15:58:33 +08:00

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

看注释。

phx13ye

2015-05-19 16:53:49 +08:00

@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

2015-05-19 17:04:07 +08:00

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