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

Question

这是一道作业题，二分查找已经介绍过了:

Given two arrays, respectively N and M elements in ascending order, not necessarily unique:
What is a time efficient algorithm to find the kth smallest element in the union of both arrays?

他们说这需要 O(logN + logM)，其中 N 和 M 是数组的长度。

让我们将数组命名为a 和b。显然我们可以忽略所有 a[i] 和 b[i] where i > k.
首先让我们比较一下 a[k/2] 和 b[k/2]。让 b[k/2] > a[k/2]。因此我们也可以丢弃所有 b[i]，其中 i > k/2。

现在我们有所有 a[i]，其中 i < k 和所有 b[i]，其中 i < k/2 可以找到答案。

下一步是什么？

Answer 1

我希望我不是在回答你的作业，因为这个问题被问到已经一年多了。这是一个尾递归解决方案，需要 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  # integer division
    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)

请注意，我的解决方案是在每次调用时创建较小数组的新副本，这可以通过仅传递原始数组的开始和结束索引轻松消除。