45

给定两个长度为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 ) 时间内解决。

4

4 回答 4

14

正确的 O(n) 解决方案相当复杂，需要大量的文本、代码和技巧来解释和证明。更准确地说，它需要 3 页才能令人信服地做到这一点，可以在此处详细查看http://www.cse.yorku.ca/~andy/pubs/X+Y.pdf（simonzack在评论中找到）。

它基本上是一种聪明的分治算法，除其他外，它利用了这样一个事实，即在排序的 n×n 矩阵中，可以找到O(n)小于/大于给定数量的元素数量k. 它递归地将矩阵分解为更小的子矩阵（通过仅采用奇数行和列，产生具有列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)中小于/大于给定数字的数字数量。请记住，我们不需要实际的矩阵！正如 OP 所描述的，两个 size 数组的笛卡尔和产生一个排序矩阵，我们可以通过考虑数组的元素来模拟它，如下所示：kn-by-nnn-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，有多少个大于 。显然，如果两个值都小于(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一部分。二进制搜索！正如其他答案/评论中提到的那样，中位数必须是此数组中包含的值：

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

只需对该数组 [also O(n*logn)] 进行排序，然后对其运行二进制搜索。由于数组现在处于非递减顺序，因此可以直接注意到小于每个的数字的数量candidate[i]也是非递减值（单调函数），这使其适用于二分查找。k = candidate[i]结果smaller_than_k(k)返回小于的最大数(n²+1)/2就是答案，并且在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
}
于 2013-06-27T02:05:50.890 回答
1

假设数组是A = {A[1] ... A[n]}, 和B = {B[1] ... B[n]}, 成对和数组是C = {A[i] + B[j], where 1 <= i <= n, 1 <= j <= n}包含n^2元素的数组，我们需要找到它的中位数。

Median ofC必须是数组的一个元素D = {A[1] + B[n], A[2] + B[n - 1], ... A[n] + B[1]}：如果您修复A[i]并考虑所有 sums 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 的算法将起作用。

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

于 2013-06-27T00:52:32.190 回答
0

您应该使用选择算法在 O(n) 中找到未排序列表的中位数。看看这个：http ://en.wikipedia.org/wiki/Selection_algorithm#Linear_general_selection_algorithm_-_Median_of_Medians_algorithm

于 2013-07-02T21:45:33.823 回答
0

这不起作用吗？：

只要A和B已排序，您就可以在线性时间内计算数字的排名。您用于计算等级的技术也可用于查找A+B介于某个下限和某个上限之间的所有事物，这些事物在时间上与输出的大小成线性关系加上|A|+|B|。

从. n_ A+B取中位数，比如说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++.
}

进一步编辑：实际上，上述技巧仅将候选空间缩小到大约 n log(n) 的成员A+B。那么你有一个在大小为 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| 记录 |A|。但是然后你再做一次，你会得到一个大约为 sqrt(n) polylog(n) 的范围。

于 2013-06-27T01:23:50.450 回答