小编Adi*_*tya的帖子

给出了两个长度为n的排序数组,问题是在O(n)时间内找到它们的和数组的中值,它包含数组A的每个元素和数组B的每个元素之间的所有可能的成对和.

例如:令A [2,4,6]和B [1,3,5]为两个给定的数组.sum数组是[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)时间内解决.