找出数组元素求和的中位数

Question

给定长度为n的两个已排序数组，问题是在O(n)时间内查找它们的总和数组的中位数，该数组包含数组A的每个元素和数组B的每个元素之间所有可能的成对求和。

例如：让A [2,4,6]和B [1,3,5]成为给定的两个数组。和数组是[2+1,2+3,2+5,4+1,4+3,4+5,6+1,6+3,6+5]。在O(n)中找到此数组的中位数。

以O(n)方式解决问题相当直观，但是否存在O(n)的解决方案？

注意：这是面试中向我的一个朋友提出的问题，面试官非常确定可以在O(n)的时间内解决。

- Aditya

---

你知道总和的中位数是否等于中位数之和吗？ - GameAlchemist

注意，OP所说的数组求和更像是笛卡尔积，结果数组包含N*N个元素。 - Mikhail

咳，这确实是可能的（Mirzaian–Arjomandi 1985），但期望在面试中要求使用O(n)算法是不现实的。 - David Eisenstat

@user814628 这是O(n^2)而不是O(n)。 - aaronman

这是David提到的Mirzaian-Arjomandi 1985的链接：http://www.cse.yorku.ca/~andy/pubs/X+Y.pdf。 - simonzack

Answer 1

正确的O(n)解决方案相当复杂，需要大量的文本、代码和技能来解释和证明。更确切地说，需要三页纸才能令人信服地说明这一点，详情请参见此处（由评论中的simonzack发现）。

它基本上是一个聪明的分治算法，利用了排序的n×n矩阵中可以找到比给定数字k小/大的元素数量为O(n)的事实。它将矩阵递归地分解成较小的子矩阵（通过只取奇数行和列，得到一个有n/2列和n/2行的子矩阵），再与上述步骤结合起来，结果是复杂度为O(n)+O(n/2)+O(n/4)...=O(2*n)=O(n)。真的很不可思议！

我无法比论文更好地解释它，这就是为什么我会解释一个更简单的O(n logn)解决方案 :)

---

O(n * logn) 解决方案：

这是一次面试！你不能在时间内得到那个O(n)解决方案。所以嘿，为什么不提供一个解决方案，虽然不是最优的，但比其他明显的O(n²)候选方案更好呢？

我将利用上面提到的O(n)算法，在排序的n×n矩阵中找到比给定数字k小/大的元素数量。请记住，我们不需要一个实际的矩阵！如本文所述，两个大小为n的数组的笛卡尔和结果是一个排序的n×n矩阵，我们可以通过考虑数组的元素来模拟它：

a[3] = {1, 5, 9};
b[3] = {4, 6, 8};
//a + b:
{1+4, 1+6, 1+8,
 5+4, 5+6, 5+8,
 9+4, 9+6, 9+8}

因此，每行都包含非递减的数字，每列也是如此。现在，假设你有一个数字k。我们想要在O(n)的时间内找出在这个矩阵中比k小和大的数字各有多少个。显然，如果这两个值都小于(n²+1)/2，那么k就是我们的中位数！

算法非常简单：

int smaller_than_k(int k){
    int x = 0, j = n-1;
    for(int i = 0; i < n; ++i){
        while(j >= 0 && k <= a[i]+b[j]){
            --j;
        }
        x += j+1;
    }
    return x;
}

这基本上是在每一行中计算符合条件的元素数量。由于行和列已经按照上面所示排序，这将提供正确的结果。由于i和j都最多迭代n次，因此该算法的时间复杂度为O(n) [请注意，在for循环内j没有被重置]。算法greater_than_k类似。

那么我们该如何选择k？这就是logn部分。 二分查找！正如其他回答/评论中所提到的，中位数必须是包含在此数组中的值:

candidates[n] = {a[0]+b[n-1], a[1]+b[n-2],... a[n-1]+b[0]};.

只需对此数组进行排序[也是O(n*logn)]，然后在其上运行二分查找。由于数组现在按非递减顺序排列，因此容易注意到小于每个candidate[i]的数字数量也是一个非递减的值（单调函数），这使它适合于二分搜索。返回小于k的结果小于(n²+1)/2的最大数k = candidate[i]是答案，并且可以在log(n)次迭代中获得：

int b_search(){
    int lo = 0, hi = n, mid, n2 = (n²+1)/2;
    while(hi-lo > 1){
        mid = (hi+lo)/2;
        if(smaller_than_k(candidate[mid]) < n2)
            lo = mid;
        else
            hi = mid;
    }
    return candidate[lo]; // the median
}

- i Code 4 Food

---

由于i和j均最多迭代n次，因此该算法的时间复杂度是O(n)。难道不应该是O(n²)吗？ - Khanh Nguyen

但是还有一个问题：如果我没错的话，在获得已排序的候选者之后，您会对每个候选者运行smaller_than_k(k)，直到找到那个人。这样在最坏情况下会使其成为O(n ^ 2)吧？ - Khanh Nguyen

你能详细解释一下为什么答案在“candidates”之中吗？其他答案只是给了一个想法，但我无法提供彻底的证明。 - Mikhail

中位数不一定在矩阵（给定的“candidates”矩阵）的对角线上，就像@Mikhail所想的那样。考虑[1,2,3,4]和[10,20,30,40]。candidates是[14,23,32,41]，但中位数是24和31的平均值。 - xan

你能详细说明一下“candidate”吗？我认为这不正确。 - Aseem Goyal

Answer 2

假设数组为A = {A[1] ... A[n]}和B = {B[1] ... B[n]}，配对求和数组为C = {A[i] + B[j]，其中1 <= i <= n，1 <= j <= n}，它有n^2个元素，我们需要找到它的中位数。 C的中位数必须是数组D = {A[1] + B[n]，A[2] + B[n - 1]，... A[n] + B[1]}中的一个元素：如果你固定A[i]并考虑所有的和A[i] + B[j]，你会发现唯一的A[i] + B[j = n + 1 - i]（它是D中的一个）可能是中位数。也就是说，它可能不是中位数，但如果不是，那么所有其他的A[i] + B[j]也都不是中位数。

这可以通过考虑所有的 B[j] 并计算比 A[i] + B[j] 小和大的值的数量（由于两个数组已排序，所以我们可以相当精确地进行计算——尽管计算有点混乱）。您会发现对于 A[i] + B[n + 1 - j]，这两个计数最为“平衡”。

问题就转化为找到 D 的中位数，它只有 n 个元素。 Hoare's 这样的算法将起作用。 更新: 此答案是错误的。真正的结论是 中位数 是 D 的一个元素，但是 D 的中位数 不同于 C 的中位数。

- Khanh Nguyen

---

如果你无法阅读已删除的帖子，请考虑[0 1 1 1 2]和[0 0 0 1 2]。如果我理解正确，你的“对角线”是[2 2 1 1 2]，其中位数为2。但正确的结果应该是1。 - andrew cooke

@aaronman 你（或者我）在回答错误时不必删除它。SO 没有规定你不能发布错误的答案，只要你投入足够的时间和精力。只需将其踩一下，为后来的观众留下一个注释即可。我们所做的一切都是为了贡献一个好的答案。我的答案是错误的，但这是一个想法。通过将其保留在这里，未来的观众就不会犯同样的错误（并希望通过改进它得出一个答案）。如果你没有删除你的帖子，我就不会浪费时间尝试同样的想法！ - Khanh Nguyen

@andrewcooke 一个反例很好，但如果您能指出哪一步是错误的，那就更好了。不冒犯，您的反例做得很好 :) - Khanh Nguyen

@andrewcooke 或许吧，但我发现了一个漏洞。我已经添加了更新，事实上，我一开始就应该注意到这点，我的答案从未给出过分数答案（即两个值的平均值），而当两个数组都有奇数个元素时必须发生这种情况。 - Khanh Nguyen

如果你知道答案是错误的，你应该考虑删除它。 - David Heffernan

Answer 3

这个方法行不行？：

只要A和B是排序的，就可以在线性时间内计算一个数字的排名。你用于计算排名的技术也可以用于在时间线性输出大小加上|A|+|B|的情况下找到A+B中在某个下限和某个上限之间的所有内容。

从A+B中随机抽取n个元素。取中位数，称为foo。计算foo的排名。以恒定的概率，foo的排名在中位数的排名上加减n。重复此过程（预期次数为常数），直到您对中位数的下限和上限有了相差2n的范围。（整个过程需要预期的线性时间，但显然很慢。）

现在，您只需要枚举边界之间的所有内容，并在线性大小的列表上进行线性时间选择即可。

（无关紧要的是，我不会因面试官问这样一个明显糟糕的面试问题而原谅他。像这样的东西根本不能说明您编码的能力。）

编辑：你可以通过以下方式计算一个数字x的等级：

Set i = j = 0.
While j < |B| and A[i] + B[j] <= x, j++.
While i < |A| {
  While A[i] + B[j] > x and j >= 0, j--.
  If j < 0, break.
  rank += j+1.
  i++.
}

进一步编辑：实际上，上述技巧只能将A+B的候选空间缩小到大约n log(n)个成员。然后，在大小为n log(n)的宇宙中，您可以进行一般的选择问题；您可以再次使用基本相同的技巧，并找到一个大小与sqrt(n) log(n)成比例的范围，在其中进行选择。

原因如下：如果从n集合中抽取k个物品并取中位数，则样本中位数的顺序在第(1/2-sqrt(log(n)/k))和第(1/2+sqrt(log(n)/k))个元素之间，至少具有常数概率。当n = |A+B|时，我们将希望取k = sqrt(n)，我们得到大约sqrt(n log n)个元素的范围---大约是|A| log |A|。但是，然后您再次执行此操作，您将获得一个大约为sqrt(n) polylog(n)的顺序范围。

- tmyklebu

---

因此，排名高于线性（嵌套的for循环）解决方案不是线性的。 - aaronman

通常任何带有“随机”的东西都会具有最坏情况下的无限复杂度。 - aschepler

不，排名计算显然是线性的。这被称为“拉斯维加斯”算法；它总是返回正确的答案，其期望运行时间很好。 - tmyklebu

现在你需要做的就是枚举边界之间的所有内容，并在线性大小的列表上进行线性时间选择。你计划如何计算这个列表？请记住，数字不需要很小，你的2n个数字列表可能具有10^7的下限和10^9的上限，你需要找出其中的那些数字。除此之外，你的解决方案与我的有点类似，只是我使用二分查找而不是随机算法。 - i Code 4 Food

@Arthur：你可以像计算排名一样计算列表。为每个i找到j的下限和上限，使得范围内的所有元素都位于这些边界之间。然后，您可以枚举那些重要的A+B元素。像这样的随机抽样技巧通常是击败二分搜索的关键。(作为奖励，它在实践中通常运行得更快。我也不相信它的实际用途，直到我看到有人真正使用了这样的技巧。) - tmyklebu

Answer 4

你应该使用一种选择算法在O(n)时间内找到未排序列表的中位数。可以参考这个链接：http://en.wikipedia.org/wiki/Selection_algorithm#Linear_general_selection_algorithm_-_Median_of_Medians_algorithm

- Mattia Larentis