给定2个排序的整数数组,找到次线性时间中的第n个最大数

Question

可能重复:
如何在两个排序数组的并集中找到第k个最小元素？

这是一个问题,我的一位朋友告诉我他在面试时被问到,我一直在考虑解决方案.

次线性时间对我来说意味着对数,所以也许是某种分而治之的方法.为简单起见,假设两个数组的大小相同,并且所有元素都是唯一的

Answer 1

我认为这是在子阵列两个并行二进制搜索A[0..n-1]和B[0..n-1],这是O(log n)的.

• 给定排序数组,您知道第n个最大值将出现在之前或之处,A[n-1]如果它在数组中A,或者B[n-1]它是否在数组中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),但无论如何肯定是次线性的.

Answer 2

我相信您可以使用二进制搜索的变体来解决此问题.该算法背后的直觉如下.让两个数组分别为A和B,为了简单起见,我们假设它们的大小相同(这不是必需的,正如您所见).对于每个数组,我们可以构造并行数组Ac和Bc,使得对于每个索引i,Ac [i]是两个数组中不大于A [i]且Bc [i]是的数量.两个数组中不大于B [i]的元素.如果我们可以有效地构造这些数组,那么我们可以通过在Ac和Bc上进行二进制搜索来找到值k,从而有效地找到第k个最小元素.那个条目的A或B的相应条目是第k个最大元素.二进制搜索是有效的,因为两个数组Ac和Bc是排序的,我认为你可以很容易地说服自己.

当然,这种解决方案在次线性时间内不起作用,因为构造数组Ac和Bc需要O(n)时间.那么问题是 - 是否有某种方式可以隐式构建这些数组？也就是说,我们可以确定这些数组中的值而不必构建每个元素吗？我认为答案是肯定的,使用这种算法.让我们从搜索数组A开始,看它是否具有第k个最小值.我们知道第k个最小值不能出现在位置k之后的数组A中的数组中(假设所有元素都是不同的).因此,让我们只关注数组A的前k个元素.我们将对这些值进行二分搜索,如下所示.从位置k/2开始; 这是数组A中第k/2个最小的元素.现在在数组B中进行二进制搜索,找到B中最大的值小于该值,并查看它在数组中的位置; 这是B中元素的数量小于当前值.如果我们将A和B中元素的位置相加,我们将两个数组中的元素总数小于当前元素.如果这正是k,我们就完成了.如果这小于k,那么我们递归到A的前k个元素的上半部分,如果这大于k,我们在k的第一个元素的下半部分递归,等等.最后,我们要么发现第k个最大元素在数组A中,在这种情况下我们就完成了.否则,在阵列B上重复此过程.

该算法的运行时间如下.对数组A的搜索对k个元素进行二进制搜索,这需要进行O(lg k)次迭代.每次迭代都需要花费O(lg n),因为我们必须在B中进行二进制搜索.这意味着此搜索的总时间为O(lg k lg n).在数组B中执行此操作的时间是相同的,因此算法的净运行时间为O(lg k lg n)= O(lg ² n)= o(n),这是次线性的.