我有2个排序的整数数组，如何找到第k为O（LOGN）时最大的项目？ [英] I have 2 sorted arrays of integers, how do I find the kth biggest item in O(logn) time?

问题描述

有人问我在一次采访中这个问题。我能做到这一点在O（n）的时间很明显，但我不能去想办法解决在O（LOGN）。这听起来像使用一些分而治之算法，但我不知道。

I was asked this question in an interview. I was able to do it in O(n) time obviously, but I fail to think about a way to solve in in O(logn). It sounds like using some divide-and-conquer algorithms but I'm not sure.

推荐答案

既要截断大小为k。如果有必要，有计划想像足够的无穷大的一个或两个阵列年底领他们到大小为k;这会不会影响渐近运行。 （在实际实施中，我们可能会做一些更有效。）

Truncate both to size k. If necessary, have the program imagine enough infinities at the end of one or both arrays to bring them up to size k; this will not affect the asymptotic runtime. (In a real implementation, we would probably do something more efficient.)

然后，比较每个阵列的k个/ 2'th元素。如果元素进行比较平等的，我们已经找到了第k元素;否则，让与下部K / 2'th元件阵列是A和其他为B.扔掉A和下半部B的上半部分，然后递归发现的剩下第k / 2'th元件。停止的时候我们打K = 1。

Then, compare the k/2'th elements of each array. If the elements compared equal, we've found the k'th element; otherwise, let the array with the lower k/2'th element be A and the other be B. Throw away the bottom half of A and the top half of B, then recursively find the k/2'th element of what remains. Stop when we hit k=1.

在每一步中，底部A的一半是保证是太小了，和B的上半部分是保证是太大。的剩下的K / 2'th元件被保证是大于底部A的一半，所以它的保证是原始的k个元素

On every step, the bottom half of A is guaranteed to be too small, and the top half of B is guaranteed to be too big. The k/2'th element of what remains is guaranteed to be bigger than the bottom half of A, so it's guaranteed to be the k'th element of the original.

概念证明，在Python：

Proof of concept, in 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)

我已经测试过这一点，但不多。

I have tested this, but not much.

这篇关于我有2个排序的整数数组，如何找到第k为O（LOGN）时最大的项目？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！