java - 我有2个整数排序数组，如何找到O(logn)时间中的第k个最大项？

This question already has answers here:

How to find the kth smallest element in the union of two sorted arrays?

(17个答案)


6年前关闭。




采访中有人问我这个问题。我显然可以在O(n)的时间内完成此操作，但是我没有考虑在O(logn)中解决的方法。听起来好像使用了一些分治法，但是我不确定。

最佳答案

将两者都截断为大小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)

我已经测试过了，但是还不多。