求数组和的中值

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^2）中的问题非常简单，但是对于这个问题，是否有任何O（n）解决方案？

注意：这是问我的一个朋友的面试问题，面试官很确定它可以在O（n）时间内解决。

Answer 1

这不管用吗

只要对A和B进行排序，您就可以在线性时间内计算数字的秩。您用于计算秩的技术也可用于查找A B中的所有内容，这些内容在时间上界和下界之间是线性的，输出的大小加上|A||B|。

从 A B 中随机抽取 n 个事物。以中位数为例，说foo。计算 foo 的等级。在概率恒定的情况下，foo 的秩在中位数秩的 n 以内。继续这样做（预期的常量次数），直到中位数的下限和上限彼此相距2n以内。（整个过程需要预期的线性时间，但显然很慢。

你现在所要做的就是枚举边界之间的所有东西，并在线性大小的列表上进行线性时间选择。

（与此无关的是，我不会原谅面试官问了这么一个明显蹩脚的面试问题。诸如此类的东西绝不表明你的编码能力。）

编辑:您可以通过如下方式计算一个数< code>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））th和（1/2 sqrt（log（n）/k））th元素之间，具有至少恒定的概率。当n=|A B|时，我们想要取k=sqrt（n），我们得到一个大约sqrt（n log n）元素的范围——大约是|A|log|A|。但是你再做一次，你会得到一个sqrt（n）Polylog（n）顺序的范围。

Answer 2

假设数组是A={A[1]... A[n]}和B={B[1]... B[n]}，并且成对求和数组是C={A[i]B[j]，其中1

< code>C的Median必须是数组< code>D = {A[1] B[n]，A[2] B[n - 1]的一个元素，...A[n] B[1]}:如果您固定< code>A[i]，并考虑所有的和< code>A[i] B[j]，您将看到唯一的< code > A[I]B[j = n ^ 1-I](它是< code>D中的一个)可能是中间值。也就是说，它可能不是中值，但如果不是中值，则所有其他< code>A[i] B[j]也不是中值。

这可以通过考虑所有的< code>B[j]并计算小于的值的数量和大于< code>A[i] B[j]的值的数量来证明(我们可以非常准确地做到这一点，因为两个数组是排序的-计算有点混乱)。您会看到，对于< code > A[I]B[n ^ 1-j]，这两个计数是最“平衡”的。

然后，问题简化为寻找只有< code>n个元素的< code>D的中值。像霍尔这样的算法是可行的。

更新：这个答案是错误的。这里真正的结论是，中值是D的元素之一，但D“中值”与C“中值”不同。

Answer 3

正确的O（n）解决方案非常复杂，需要大量的文本，html" target="_blank">代码和技能来解释和证明。更确切地说，需要3页才能令人信服地做到这一点，正如在这里 http://www.cse.yorku.ca/~andy/pubs/X Y.pdf（由simonzack在评论中找到）的详细情况所示。

它基本上是一个聪明的分治算法，其中利用了这样一个事实，即在一个n乘n排序的矩阵中，可以在< code>O(n)中找到小于/大于给定数< code>k的元素的数量。它递归地将矩阵分解成更小的子矩阵(通过仅取奇数行和列，得到具有< code>n/2列和< code>n/2行的子矩阵),与上面的步骤结合，得到复杂度为< code>O(n) O(n/2) O(n/4)...= O(2*n) = O(n)。太疯狂了。

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

这是一次采访！你无法及时得到O（n）解决方案。那么，嘿，为什么不提供一个解决方案，尽管不是最佳的，但表明你可以比其他明显的O（n²）候选者做得更好？

我将利用上面提到的O（n）算法，在排序的n-by-n矩阵中查找小于/大于给定数字k的数字数量。请记住，我们不需要实际的矩阵！如OP所述，两个大小为n的数组的笛卡尔和产生一个排序的n-by-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，有多少个大于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）[注意j不会在for循环中重置]。greater_than_k算法类似。

现在，我们如何选择k？这就是logn部分。二进制搜索！如其他答案/评论中所述，中值必须是该数组中包含的值：

候选[n]={a[0]b[n-1]， a[1]b[n-2]，... a[n-1]b[0]}；。

只需对这个数组进行排序[也就是< code>O(n*logn)]，并对其运行二分搜索法。由于数组现在处于非递减顺序，因此很容易注意到小于每个< code>candidate[i]的数的数量也是一个非递减值(单调函数)，这使得它适用于二分搜索法。其结果< code > small _ than _ k(k)返回小于< code >(n-1)/2 的最大数< code>k = candidate[i]是答案，并且在< code>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
}