如何在两个已排序数组的并集中找到第 k 个最小元素?

问题描述：

这是一道作业题，二分查找已经介绍过了:

This is a homework question, binary search has already been introduced:

给定两个数组，分别是N和M个元素，按升序排列，不一定唯一:
在两个数组的联合中找到 k 个最小元素的时间效率算法是什么?

Given two arrays, respectively N and M elements in ascending order, not necessarily unique:
What is a time efficient algorithm to find the kth smallest element in the union of both arrays?

他们说它需要 O(logN + logM) 其中 N 和 M 是数组长度.

They say it takes O(logN + logM) where N and M are the arrays lengths.

让我们将数组命名为 a 和 b.显然我们可以忽略所有 a[i] 和 b[i] 其中 i >k.
首先让我们比较 a[k/2] 和 b[k/2].让 b[k/2] >a[k/2].因此，我们也可以丢弃所有 b[i]，其中 i >k/2.

Let's name the arrays a and b. Obviously we can ignore all a[i] and b[i] where i > k.
First let's compare a[k/2] and b[k/2]. Let b[k/2] > a[k/2]. Therefore we can discard also all b[i], where i > k/2.

现在我们有了所有的 a[i]，其中 i b[i]，其中 i

Now we have all a[i], where i < k and all b[i], where i < k/2 to find the answer.

下一步是什么?

答

你已经明白了，继续！并小心索引...

You've got it, just keep going! And be careful with the indexes...

为了简化一点，我假设 N 和 M > k，所以这里的复杂度是 O(log k)，也就是 O(log N + log M).

To simplify a bit I'll assume that N and M are > k, so the complexity here is O(log k), which is O(log N + log M).

伪代码:

i = k/2
j = k - i
step = k/4
while step > 0
    if a[i-1] > b[j-1]
        i -= step
        j += step
    else
        i += step
        j -= step
    step /= 2

if a[i-1] > b[j-1]
    return a[i-1]
else
    return b[j-1]

为了演示，你可以使用循环不变式 i + j = k，但我不会做你所有的作业:)

For the demonstration you can use the loop invariant i + j = k, but I won't do all your homework :)

如何在两个已排序数组的并集中找到第 k 个最小元素?

相关推荐