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

  • Z时代
  • 2024-01-10
  • 分类：问答

我正在研究有关在leetcode中在两个排序数组的联合中找到第k个最小元素的文章。我认为该算法不正确。有这样一行： 。对任何人来说i，怎么可能是真的j？

其次，这条线也让我 困惑：

，尽管事实确实如此。谁能解释原因？我真的很想了解算法，我通过合并数组来做到这一点，但是O(N)与O(log N)这里的时间相比，这需要时间。

回答：

我们观察到Ai < Bj，什么时候一定是正确的Ai < Bj-1。另一方面，如果Bj < Ai，那么Bj <

Ai-1..哪一个i和j怎么成立？

并非所有对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最小元素

在array中B，j元素小于Bj，在array中A，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元素B不大于Ai，并且它们都严格小于，并且我们的m <=

i元素中A的严格小于Ai（m如上所述）和未知数，但至少i-m+1等于Ai。因此j + m <= j + i =

k-1，两个数组中恰好有元素严格小于Ai，并且至少j + m + (i-m+1) = j+i+1 =

k不大于Ai，因此两个数组中第k个最小的元素等于Ai。

在情况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-1从该阵列B，并继续执行，而不重复。

所发生的所有变化是，必须用弱的不平等代替一些严格的不平等。

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

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)

以上是 在排序数组的并集中找到第k个最小的元素 的全部内容， 来源链接： utcz.com/qa/401350.html

回到顶部