4 回答

• 0

  正确的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) . 太疯狂了！

  我无法解释它比论文更好， which is why I'll explain a simpler, O(n logn) solution instead :) .

  ---

  O（n * logn）解决方案：

  It's an interview! 你无法及时得到那个 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 ，有多少数字更大 . 显然，如果两个值都小于 (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 部分 . Binary Search! 正如其他答案/评论中所提到的，中位数必须是此数组中包含的值：

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

  只需对此数组[也 O(n*logn) ]进行排序，然后对其运行二进制搜索 . 由于数组现在处于非递减顺序，因此可以直截了当地注意到小于每个 candidate[i] 的数字量也是非递减值（单调函数），这使得它适合于二进制搜索 . 其结果 smaller_than_k(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
  }
  

  回复于 2024-05-03T19:41:24+08:00
• 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 元素，我们需要找到它的中位数 .

  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] 来计算，并计算 lower 的值的数量和 greater 的值的数量，而不是 A[i] + B[j] （我们可以非常准确地做到这一点，因为这两个数组已经排序 - 计算有点混乱的想法） . 你会看到 A[i] + B[n + 1 - j] 这两个计数最多"balanced" .

  然后问题减少到找到中位数 D ，只有 n 个元素 . 诸如Hoare's的算法将起作用 .

  UPDATE ：这个答案错了 . 这里真正的结论是 median 是 D 元素中的一个，但是 D 的中位数与 C 的中位数不同 .

  回复于 2024-05-03T19:41:24+08:00
• 0

  这不行吗？：

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

  从 A+B 随机抽样 n . 取中位数，比如 foo . 计算 foo 的等级 . 在概率恒定的情况下， foo 的等级在中位数的 n 之内 . 继续这样做（预期的常数次数），直到你的中位数的下限和上限在彼此的 2n 之内 . （整个过程需要预期的线性时间，但显然很慢 . ）

  您现在要做的就是枚举边界之间的所有内容，并在线性大小的列表上进行线性时间选择 .

  （不相关的，我不会原谅面试官问这么明显糟糕的面试问题 . 这样的东西绝不表示你的编码能力 . ）

  EDIT ：您可以通过执行以下操作来计算数字 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++.
  }
  

  FURTHER EDIT ：实际上，上述技巧只会将候选空间缩小到大约n个log（n） A+B 成员 . 然后在大小为n log（n）的Universe中存在一般选择问题;你可以再做一次基本相同的技巧，找到一个与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）的范围 .

  回复于 2024-05-03T19:41:24+08:00
• 14

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

  回复于 2024-05-03T19:41:24+08:00