我有两个已排序的整数数组，如何在O(logn)时间内找到第k大的项？

Question

我在面试中被问到了这个问题。显然，我能够在O(n)的时间内解决它，但我无法想出一种在O(logn)时间内解决它的方法。听起来像是使用了一些分治算法，但我不确定。

- user3342802

---

你能提供一下你是如何以O(n)的时间复杂度完成的吗？你是在两者之间来回跳转吗？ - ChiefTwoPencils

坦白地说，我不认为它会比O(k)更少：您需要比较两个数组的最后一个元素，并递减与其中较大项相关联的索引。重复这个过程k次，就可以得到第k大的元素。 - JB Nizet

Answer 1

将两个数组都截取到大小为k。如果需要，让程序想象足够多的无穷大数放在其中一个或两个数组的末尾，以使它们达到大小k；这不会影响渐进运行时间。（在实际实现中，我们可能会做更有效的事情。）

然后，比较每个数组的第k/2个元素。如果比较的元素相等，我们就找到了第k个元素；否则，让具有较低k/2个元素的数组为A，另一个为B。丢弃A的底半部分和B的顶半部分，然后递归地找出剩余部分的第k/2个元素。当k=1时停止。

在每个步骤中，A的底部一半保证过小，B的顶部一半保证过大。剩下的第k/2个元素保证比A的底半部分大，因此它保证是原始的第k个元素。

Python中的概念证明：

def kth(array1, array2, k):
    # Basic proof of concept. This doesn't handle a bunch of edge cases
    # that a real implementation should handle.
    # Limitations:
    #   Requires numpy arrays for efficient slicing.
    #   Requires k to be a power of 2
    #   Requires array1 and array2 to be of length exactly k
    if k == 1:
        return min(array1[0], array2[0])
    mid = k//2 - 1
    if array1[mid] > array2[mid]:
        array1, array2 = array2, array1
    return kth(array1[k//2:], array2[:k//2], k//2)

我已经测试过这个功能，但是还不太充分。

- user2357112

---

听起来像是。+1。 - JB Nizet

如果比较的元素相等，则任意选择：如果两个元素相等，难道你没有找到第k大的元素吗？ - JB Nizet

@JBNizet：我认为你是对的。 - user2357112

我正在尝试实现这个算法，但似乎找到了一个该算法失败的情况。考虑数组 A = {1} 和 B = {2, 3}，并尝试查找第二大的元素（应该是 2）。当你将 A 扩展为大小为两个元素 A = {1, ∞}，将其在中心分成两半 {1 | ∞}，然后删除 A 的右半部分和 B 的左半部分，你会得到 A = {1} 和 B = {3}，它们的最小值为 1。 - 1110101001

可能是从0开始索引和从1开始索引的问题。我的描述似乎是从1开始索引的。你应该删除A的左半部分和B的右半部分，而不是反过来。 - user2357112