如何在两个排序数组的并集中找到第k个最小元素？

Question

这是一个作业问题。他们说这需要O(logN + logM)在哪里N，M是数组的长度。让我们命名的数组a和b。显然，我们可以忽略所有a[i]和b[i]其中i>ķ。首先，我们比较a[k/2]和b[k/2]。让b[k/2]> a[k/2]。因此，我们也可以丢弃所有b[i]，其中i> k / 2。现在我们有了a[i]i <k和all> b[i]i <k / 2的全部，以找到答案。你下一步怎么做？

Answer 1

您已掌握，继续前进！并注意索引...

为了简化一点，我将假设N和M> k，因此这里的复杂度为O（log k），即O（log N + log M）。

伪代码：

i = k/2

j = k - i

step = k/4

while step > 0

    if a[i-1] > b[j-1]

        i -= step

        j += step

    else

        i += step

        j -= step

    step /= 2

if a[i-1] > b[j-1]

    return a[i-1]

else

    return b[j-1]

为了演示，您可以使用循环不变i + j = k，但我不会做所有作业：)

Answer 2

自问这个问题以来已经过去了一年多，我希望我不回答您的作业。这是尾部递归解决方案，将花费log（len（a）+ len（b））时间。

假设：输入正确。即k在[0，len（a）+ len（b）]范围内

基本案例：

如果数组之一的长度为0，则答案为第二个数组的第k个元素。

减少步骤：

如果中指a+中指b小于k

如果的中间元素a大于的中间元素b，我们可以忽略的前一半b，进行调整k。

否则忽略上半年的a调整k。

否则，如果k小于和的中间索引之a和b：

如果中的元素a大于中的元素b，我们可以放心地忽略中的后一半a

否则我们可以忽略 b

码：

def kthlargest(arr1, arr2, k):

    if len(arr1) == 0:

        return arr2[k]

    elif len(arr2) == 0:

        return arr1[k]

    mida1 = len(arr1)/2

    mida2 = len(arr2)/2

    if mida1+mida2<k:

        if arr1[mida1]>arr2[mida2]:

            return kthlargest(arr1, arr2[mida2+1:], k-mida2-1)

        else:

            return kthlargest(arr1[mida1+1:], arr2, k-mida1-1)

    else:

        if arr1[mida1]>arr2[mida2]:

            return kthlargest(arr1[:mida1], arr2, k)

        else:

            return kthlargest(arr1, arr2[:mida2], k)

请注意，我的解决方案是在每次调用中创建较小数组的新副本，只需在原始数组上传递开始和结束索引即可轻松消除这种情况。