一种在两个大小为n的数组中找到第n个最大数的算法

Question

我有这个问题:

给定大小为n的两个排序列表(存储在数组中),找到一个O(log n)算法,该算法计算两个列表的并集中的第n个最大元素.

我可以看到这里可能有一个技巧,因为它需要第n个最大的元素,并且数组的大小也是n,但我无法弄清楚它是什么.我以为我可以适应计数排序,那会有用吗？

Answer 1

比较A [n/2]和B [n/2].如果相等,其中任何一个都是我们的结果.此算法的其他停止条件是两个数组的大小均为1(最初或在几个递归步骤之后).在这种情况下,我们只选择A [n/2]和B [n/2]中最大的一个.

如果A [n/2] <B [n/2],则对A []的后半部分和B []的前半部分递归重复此过程.

如果A [n/2]> B [n/2],则对B []的后半部分和A []的前半部分递归重复此过程.

由于在每一步中问题大小(在最坏的情况下)减半,我们将得到O(log n)算法.

始终将数组大小除以2以使索引只有在2 n的幂时才能正常工作.选择索引(任意n)的更正确的方法是对一个数组使用相同的策略,但选择补充索引:j=n-i对于另一个.