在两个排序数组的合并数组中查找中位数

Question

假设我们有 2 个排序的整数数组，大小为 n 和 m。查找所有 m + n 个数字的中位数的最佳方法是什么？

这很容易做到 log(n) * log(m) 复杂。但我想在 log(n) + log(m) 时间内解决这个问题。那么有什么解决这个问题的建议吗？

Answer 1

是的，这是可以做到的。给定两个数组 A 和 B，在最坏的情况下，您必须首先在 A 中执行二分查找，然后，如果失败，则在 [=11] 中执行二分查找=] 寻找中位数。在二进制搜索的每一步中，您检查当前元素是否实际上是合并的 A+B 数组的中位数。这种检查需要常数时间。

让我们看看为什么这样的检查是不变的。为简单起见，我们假设 |A| + |B| 是一个奇数，并且两个数组中的所有数字都不同。您可以稍后通过应用通常的中值定义方法来删除这些限制（即，如何计算包含重复项的数组或具有偶数长度的数组的中值）。无论如何，鉴于此，我们可以肯定地知道，在合并后的数组中，实际中位数的左右两侧将有 (|A| + |B| - 1) / 2 个元素。在A中的二分查找过程中，我们知道当前元素x在数组A中的索引（假设为i）。现在，如果 x 满足条件 B[j] < x < B[j+1]，其中 i + j == (|A| + |B| - 1) / 2，那么 x 就是你的中位数。

总体复杂度为 O(log(max(|A|, |B|)) 时间和 O(1) 内存。

Answer 2

取列表A中的中值元素并将其命名为a。将 a 与列表 B 中的中心元素进行比较。让我们称它们为 b1 和 b2（如果 B 的长度为奇数，那么拆分 b 的确切位置取决于您对偶数长度列表的中位数的定义，但无论如何过程几乎相同）。如果 b1≤a≤b2 那么 a 是合并数组的中位数。这可以在常数时间内完成，因为它只需要两次比较。

如果 a 大于 b2，那么我们将 A 的上半部分添加到 B 的顶部并重复。 B 将不再被排序，但没关系。如果 a 小于 b1，那么我们将 A 的下半部分添加到 B 的底部并重复。这些将最多迭代 log(n) 次（当然，如果中位数早点找到则停止）。

这可能找不到中位数。如果是这种情况，则中位数在 B 中。如果是这样，请执行相同的算法，将 A 和 B 反转。这将需要 log(m) 次迭代。总共你将最多执行 2*(log(n)+log(m)) 次常数时间操作的迭代，所以你已经按顺序解决了问题 log(n)+log(m) time.

这与 iehrlich 给出的答案基本相同，但写得更明确。

Answer 3

说明

这道题的重点是通过比较剩下的A和B的中位数，每一步递归忽略掉A和B的一半：

if (aMid < bMid) Keep [aMid  +1 ... n] and [bLeft ... m]    
else Keep [bMid + 1 ... m] and [aLeft ... n]
// where n and m are the length of array A and B

如下：时间复杂度为O(log(m + n))

public double findMedianSortedArrays(int[] A, int[] B) {
    int m = A.length, n = B.length;
    int l = (m + n + 1) / 2;
    int r = (m + n + 2) / 2;
    return (getkth(A, 0, B, 0, l) + getkth(A, 0, B, 0, r)) / 2.0;
}

public double getkth(int[] A, int aStart, int[] B, int bStart, int k) {
    if (aStart > A.length - 1) return B[bStart + k - 1];            
    if (bStart > B.length - 1) return A[aStart + k - 1];                
    if (k == 1) return Math.min(A[aStart], B[bStart]);

    int aMid = Integer.MAX_VALUE, bMid = Integer.MAX_VALUE;
    if (aStart + k/2 - 1 < A.length) aMid = A[aStart + k/2 - 1]; 
    if (bStart + k/2 - 1 < B.length) bMid = B[bStart + k/2 - 1];        

    if (aMid < bMid) 
        return getkth(A, aStart + k / 2, B, bStart, k - k / 2); // Check: aRight + bLeft 
    else 
        return getkth(A, aStart, B, bStart + k / 2, k - k / 2); // Check: bRight + aLeft
}

希望对您有所帮助！如果您需要对任何部分进行更多解释，请告诉我。

Answer 4

Here's a very good solution I found in Java on Stack Overflow.这是一种在两个数组中找到K和K+1个最小项的方法，其中K是合并数组的中心。

如果你有一个函数可以找到两个数组的第 K 项，那么找到这两个数组的中位数就很容易了；

计算X和Y的第K项和第K+1项的加权平均值

但是你需要一种方法来找到两个列表中的第 K 个项目；（记住我们现在是一个索引）

如果 X 包含零项，则 X 和 Y 的第 K 个最小项是 Y 的第 K 个最小项
否则，如果 K == 2，则 X 和 Y 的第二小项是 X 和 Y 的最小项中的最小项 (min(X[0], Y[0]))
否则;

我。设 A 为 min(length(X), K / 2)

二。设 B 为 min(length(Y), K / 2)

三。如果 X[A] > Y[B] 则从步骤 1 递归。使用 X、Y' 和 Y 的所有元素从 B 到 Y 的末尾并且 K' = K - B，否则使用 X' 和所有元素递归从 A 到 X、Y 和 K' 末尾的 X = K - A

如果我明天找到时间，我将验证此算法是否按规定在 Python 中工作，并提供示例源代码，它可能会按原样出现一些差一错误。

在两个排序数组的合并数组中查找中位数

Finding median in merged array of two sorted arrays

algorithm

time-complexity

median

data-structures