我有2个排序的整数数组,如何在O(logn)时间内找到第k个最大的项目？

Question

我在接受采访时被问到这个问题.我明显可以在O(n)时间内完成它,但我没有考虑在O(logn)中解决问题的方法.这听起来像使用一些分而治之的算法,但我不确定.

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)

我测试了这个,但并不多.