4

我正在研究有关在leetcode的两个排序数组的联合中查找第 k 个最小元素的文章。我不认为该算法是正确的。有这样一行：我们观察到当 Ai < Bj 时，Ai < Bj-1 一定是真的。另一方面，如果 Bj < Ai，则 Bj < Ai-1。. 怎么可能对任何i和都是真的j？

其次，这条线也让我感到困惑：我们试图通过比较 A 和 B 的中间元素来解决这个棘手的问题，我们将其识别为 Ai 和 Bj。如果 Ai 在 Bj 和 Bj-1 之间，我们刚刚找到了第 i+j+1 个最小元素，尽管结果是正确的。谁能解释原因？我真的很想了解算法，我已经通过合并数组来完成它，但是与这里的O(N)时间相比，这需要时间O(log N)。

4

2 回答 2

7

您正在孤立地解释这些陈述，但它们是相互建立的。这是（我认为）您所指的文本：

保持不变量 i + j = k – 1，如果 Bj-1 < Ai < Bj，则 Ai 必须是第 k 个最小的，否则如果 Ai-1 < Bj < Ai，则 Bj 必须是第 k 个最小的. 如果满足上述条件之一，我们就完成了。如果没有，我们将使用 i 和 j 作为枢轴索引来细分数组。但是怎么做？我们应该丢弃哪一部分？Ai 和 Bj 本身呢？

我们观察到，当 Ai < Bj 时，Ai < Bj-1 一定是真的。另一方面，如果 Bj < Ai，则 Bj < Ai-1。为什么？

将其分解为子命题会产生以下解释（请记住，索引从 开始0，但这A0是第一个最小的项目，并且A1是第二小的项目，依此类推）：

  1. i + j = k - 1（不变的，根据定义）
  2. 假设Bj-1 < Ai < Bj. 那么Ai必须是k最小的。这是因为Aiis 大于iitems inA并且大于jitems in B。所以它大于i + j = k - 1项目的总数。这意味着它在合并列表中的索引将是，因此它将是该列表中的第 th 项。A|Bk - 1k
  3. 假设Ai-1 < Bj < Ai. 然后Bj必须是第kth 最小的，根据 2 中的相同推理。
  4. 现在假设 (a)Bj-1 < Ai < Bj和 (b)Ai-1 < Bj < Ai都是false。那么很明显，如果Ai < Bjthen A1 < Bj-1，因为否则 (a) 将为真。同样，如果Bj < Aithen Bj < Ai-1，因为否则， (b) 将为真。

我相信你的话，你想要解释这些陈述而不是整个算法。（但如果你愿意，我会说更多。）

另请注意，正如Daniel Fischer的回答提醒我的那样，上述推理仅在没有重复项的情况下成立；称该命题为 0。

于 2012-09-23T20:24:50.483 回答
4

我们观察到什么时候Ai < Bj，那么它一定是真的Ai < Bj-1。另一方面，如果Bj < Ai，那么.. 对于任何和Bj < Ai-1怎么可能是真的？ij

并非所有对i和都是如此j。文章考虑了一种特殊情况。

首先，假设没有重复，即使是 和 的共同元素也A没有B。二、结论是

Ai < Bj ==> Ai < Bj-1,   resp.  Bj < Ai ==> Bj < Ai-1

是在以下条件下做出的

Bj-1 < Ai < Bj  resp. Ai-1 < Bj < Ai

持有。因此，通过排除这些配置，Ai < Bj ==> Ai <= Bj-1并Bj < Ai ==> Bj <= Ai-1立即遵循，然后严格不等式遵循不存在重复的假设。

我们尝试通过比较 A 和 B 的中间元素来解决这个棘手的问题，我们将其识别为 Ai 和 Bj。如果 Ai 在 Bj 和 Bj-1 之间，我们刚刚找到了 i+j+1 个最小元素

在 arrayB中，有j小于 的元素Bj，在 arrayA中，有i小于 的元素Ai（索引从 0 开始）。因此，如果Bj-1 < Ai < Bj，两个数组一起正好包含j + i小于 的元素Ai。

如果有重复，会有什么变化？

不多。

我们还是考虑一下情况i + j = k-1。让我们假设Ai <= Bj。

  1. 万一Ai = Bj呢？
  2. 万一Ai < Bj呢？

在情况 1. 中，设m为 的最小索引Am = Ai，以及n的最小索引Bn = Bj。然后在两个数组中，恰好有m + n <= i + j = k-1严格小于 的元素Ai，并且至少有(i+1) + (j+1) = (k+1)不大于 的元素Ai。因此，第 k 个最小的元素等于Ai。

对于 2.，我们需要考虑三种情况，a) Bj-1 < Ai、b) Bj-1 = Ai、c) Bj-1 > Ai。

在情况 a) 中，我们有不大于 的j元素，并且它们都严格小于，并且我们有严格小于(如上所述) 和未知数的元素，但至少有等于 的元素。因此，两个数组中恰好有元素严格小于，并且至少元素不大于，因此两个数组的第 k 个最小元素一起等于。BAim <= iAAimi-m+1Aij + m <= j + i = k-1Aij + m + (i-m+1) = j+i+1 = kAiAi

在情况 b) 中，同样的推理表明两个数组的第 k 个最小元素加起来等于Ai。

在剩下的情况下Ai < Bj-1，事情几乎不会变得更复杂。数组B至少j包含不大于的元素Bj-1，并且数组A至少i+1包含严格小于的元素Bj-1，因此两个数组中第 k 个最小的元素加起来最多为Bj-1。但它不能小于Ai（B最多包含j-1小于的元素Ai，因此两个数组一起最多i + (j-1) = k-2包含小于的元素Ai）。

所以我们仍然可以从数组中丢弃下面Ai的部分，从数组中丢弃A上面的部分，并继续进行，没有重复。Bj-1B

改变的只是一些严格的不等式必须用弱不等式代替。

代码（如果传递起始索引和长度而不是切片会更有效，但切片会产生更短的代码）：

def kthsmallest(A, B, k):
    if k < 1:
        return None
    a_len, b_len = len(A), len(B)
    if a_len == 0:
        return B[k-1] # let it die if B is too short, I don't care
    if b_len == 0:
        return A[k-1] # see above
    # Handle edge case: if k == a_len + b_len, we would
    # get an out-of-bounds index, since i + j <= a_len+b_len - 2
    # for valid indices i and j
    if a_len + b_len == k:
        if A[-1] < B[-1]:
            return B[-1]
        else:
            return A[-1]
    # Find indices i and j approximately proportional to len(A)/len(B)
    i = (a_len*(k-1)) // (a_len+b_len)
    j = k-1-i
    # Make sure the indices are valid, in unfortunate cases,
    # j could be set to b_len by the above
    if j >= b_len:
        j = b_len-1
        i = k-1-j
    if A[i] <= B[j]:
        if j == 0 or B[j-1] <= A[i]:
            return A[i]
        # A[i] < B[j-1] <= B[j]
        return kthsmallest(A[i:], B[:j], k-i)
    # B[j] < A[i], symmetrical to A[i] < B[j]
    if i == 0 or A[i-1] <= B[j]:
        return B[j]
    # B[j] < A[i-1]
    return kthsmallest(A[:i], B[j:], k-j)
于 2012-09-23T20:26:51.607 回答