查找数组总和的中位数
给出了两个长度为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 ）时间内解决。
正确的O（n）解决scheme相当复杂，需要大量的文本，代码和技巧来解释和certificate。 更确切地说，需要3页才能令人信服地做到这一点，详见http://www.cse.yorku.ca/~andy/pubs/X+Y.pdf （在simonzack的评论中发现）。
它基本上是一个聪明的分而治之algorithm，除其他外，利用这样一个事实，即在一个有n个sorting的matrix中，人们可以在O(n)find小于/大于比给定的数字k 。 它recursion地将matrix分解成更小的子matrix（ 通过仅取奇数行和列，产生具有n/2列和n/2行的子matrix ），结合上述步骤，导致复杂度为O(n) + O(n/2) + O(n/4)... = O(2*n) = O(n) 。 这是疯了！
我不能解释它比纸更好， 这就是为什么我会解释一个更简单的O(n logn)解决scheme:) 。
O（n * logn）解决scheme：
这是一个采访！ 你不能及时得到这个O(n)解决scheme。 所以，嘿，为什么不提供一个解决scheme，尽pipe不是最优的，这表明你可以比其他明显的O(n²)候选人做得更好？
我将利用上面提到的O(n)algorithm来找出sorting的n-by-nmatrix中小于/大于给定数目k数字的数量。 请记住，我们不需要一个实际的matrix！ 由OP描述的两个大小为n数组的笛卡尔和产生了一个有n-by-n个sorting的matrix，我们可以通过考虑数组的元素来模拟如下：
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)find这个matrix中有多less个数小于k ，有多less是更大的。 显然，如果两个值都小于(n²+1)/2 ，那就意味着k是我们的中位数！
该algorithm非常简单：
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; }
这基本上是计算每行有多less元素符合条件。 由于行和列已经按照上面的顺序sorting，这将提供正确的结果。 由于i和j每次迭代至多n次，algorithm是O(n) [ 请注意， j在for循环中不会被重置 ]。 greater_than_kalgorithm类似。
现在，我们如何selectk ？ 这是logn部分。 二进制search！ 正如其他答案/评论中提到的，中位数必须是包含在该数组中的值：
candidates[n] = {a[0]+b[n-1], a[1]+b[n-2],... a[n-1]+b[0]}; 。
简单地sorting这个数组[也是O(n*logn) ]，然后运行二进制search。 由于数组现在处于非递减顺序，所以直接注意到比每个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 }
假设数组为A = {A[1] ... A[n]} ， B = {B[1] ... B[n]} ，成对和数组为C = {A[i] + B[j], where 1 <= i <= n, 1 <= j <= n}有n^2元素，我们需要find它的中值。
C中间值必须是数组D = {A[1] + B[n], A[2] + B[n - 1], ... A[n] + B[1]}的元素：if你修复A[i] ，并考虑所有的和A[i] + B[j] ，你会看到唯一的 A[i] + B[j = n + 1 - i] （这是D ） 可能是中位数。 也就是说，它可能不是中位数，但如果不是中位数，那么所有其他A[i] + B[j]也不是中位数。
这可以通过考虑所有的B[j]来certificate，并且计算值 更低 的值的数量和 大于 A[i] + B[j] 的值的数量 （我们可以相当准确地做到这一点，因为这两个数组是sorting的 – 计算是有点混乱的想法）。 你会看到，对于A[i] + B[n + 1 - j]这两个数字是最“平衡的”。
这个问题然后简化为find只有n元素的D中位数。 像Hoare这样的algorithm是可行的。
更新 ：这个答案是错误的。 这里的真正结论是中位数是D的一个元素，但是D的中位数与C的中位数不一样。
这不正常吗？
只要A和Bsorting，就可以在线性时间内计算一个数的等级。 你用来计算等级的技术也可以用来找出A+B中所有的东西在一些下界和一些上界之间的时间线性的输出的大小加上|A|+|B| 。
从A+B随机抽样n件东西。 取中位数，说foo 。 计算foo的等级。 以恒定的概率， foo的等级在中位数的n的范围内。 继续这样做（预期的不变次数），直到你的中位数的上限和下限在彼此的2n之内。 （整个过程需要预期的线性时间，但是显然很慢。）
现在你所要做的就是列举所有边界之间的所有内容，并在线性大小的列表上进行线性时间select。
（不相关的是，我不会原谅面试官提出这样一个显而易见的面试问题，这样的东西绝不意味着你的编码能力。）
编辑 ：你可以通过做这样的事情来计算一个数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）的宇宙中有一个普遍的select问题。 你可以再做一次基本相同的技巧，find一个大小与sqrt（n）log（n）成正比的范围，在那里你做select。
原因如下：如果从n集中抽样k个东西并取中位数，则样本中位数的顺序介于（1/2 – sqrt（log（n）/ k））和（1/2 + sqrt （log（n）/ k））个元素，其概率至less为常数。 当n = | A + B |时，我们需要取k = sqrt（n），我们得到一个约为sqrt（n log n）个元素的范围—即| A | 日志| A |。 但是，你再次做，你得到的sqrt（n）polylog（n）的顺序范围。
您应该使用selectalgorithm来查找O（n）中未sorting列表的中位数。 看看这个： http : //en.wikipedia.org/wiki/Selection_algorithm#Linear_general_selection_algorithm_-_Median_of_Medians_algorithm
