给定2个整数排序数组，找到次线性时间中的第n个最大数字[重复]
问题内容：
这是我的一个朋友告诉我的一个问题，在面试时有人问他，我一直在考虑解决方案。
亚线性时间对我来说是对数的，所以也许是某种分而治之的方法。为了简单起见，假设两个数组的大小相同，并且所有元素都是唯一的
问题答案：
我认为这是对子数组A[0..n-1]和的两个并发二进制搜索B[0..n-1]，即O（log n）。
- 给定排序数组，您知道 第n个 最大数组将出现
A[n-1]在array 之前或之后的某个位置A，或者B[n-1]是否在array中B - 考虑索引
a中的A项目和索引b中的项目B。 - 如下执行二进制搜索（相当粗糙的伪代码，不考虑“一次性”问题）：
- 如果为
a + b > n，则减少搜索集 - 如果是的
A[a] > B[b]话b = b / 2，否则a = a / 2 - 如果为
a + b < n，则增加搜索集 - 如果
A[a] > B[b]那么b = 3/2 * b，其他a = 3/2 * a（中途之间a和以前a） - 如果
a + b = n那么第 n 大是max(A[a], B[b])
- 如果为
我相信最坏的情况是O（ln n），但无论如何肯定是亚线性的。
