我相信有一种方法可以在O(n)中找到长度为n的未排序数组中的第k个最大元素.或许它是"预期的"O(n)或其他东西.我们应该怎么做？
给出了两个长度为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)时间内解决.