如何找到两个数组排序的工会第k个最小的元素？

本文介绍了如何找到两个数组排序的工会第k个最小的元素？的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

这是一个家庭作业的问题。他们说，需要 O（logN个+ logM），其中 N 和 M 是数组的长度。

This is a homework question. They say it takes O(logN + logM) where N and M are the arrays lengths.

让我们命名的数组 A 和 B 。显然，我们可以忽略所有 A [1] 和 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 [1] ，其中i＆LT; k和所有的 B [I] ，其中i＆LT;克/ 2中找到了答案。

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（日志K），这是为O（log N + 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).

伪code：

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 :)