列表中位数

Question

有人问我这个问题:

您将获得两个整数列表,每个整数都按升序排序,每个整数的长度为n.两个列表中的所有整数都不同.您希望找到两个列表的并集的第n个最小元素.(也就是说,如果您连接列表并按升序对结果列表进行排序,则该元素将位于第n个位置.)

我的解决方案:假设列表是0索引的.

O(n)解决方案:一个直接的解决方案是观察数组已经排序,因此我们可以合并它们,并在n步之后停止.第一个n-1元素不需要复制到新数组中,因此该解决方案需要O(n)时间和O(1)内存.

O(log2 n)解决方案:O(log2 n)解决方案在每个列表上使用交替二分搜索.简而言之,它采用第一个列表(l1 [p1])中当前搜索间隔中的中间元素,并在l2中搜索它.由于元素是唯一的,我们将找到最多2个最接近l1 [p1]的值.根据它们相对于l1 [p1-1]和l1 [p1 + 1]及其指数p21和p22的值,我们要么返回第n个元素,要么递归:如果是(最多)3中的任何一个的总和l1中的索引可以与l2中的(最多)2个索引中的一个组合,以便l1 [p1']和l2 [p2']在两个列表的排序并集中彼此相邻并且p1'+ p2'= n或p1'+ p2'= n + 1,我们返回5个元素中的一个.如果p1 + p2> n,我们在l1中递归搜索间隔的左半部分,否则我们递归到正确的间隔.这样,对于l1中的O(log n)个可能的中点,我们在l2中进行O(log n)二进制搜索.因此运行时间为O(log2 n).

O(log n)解决方案:假设列表l1和l2对其任何元素具有持续访问时间,我们可以使用修改版本的二进制搜索来获得O(log n)解决方案.最简单的方法是在其中一个列表中搜索索引p1,并在另一个列表中计算相应的索引p2,以便始终p1 + p2 = n.(这假定列表是从1开始索引的.)首先,我们检查一个列表的所有元素都小于另一个列表中的任何元素的特殊情况:如果l1 [n] <l2 [0]返回l1 [n].如果l2 [n] <l1 [0]返回l2 [n].如果我们在此步骤之后找不到第n个最小元素,请使用近似伪代码调用findNth(1,n):

findNth(start,end)
p1 = (start + end)/2
p2 = n-p1
if l1[p1] < l2[p2]:
    if l1[p1 + 1] > l2[p2]:
        return l2[p2]
    else:
        return findNth(p1+1, end)
else:
    if l2[p2 + 1] > l1[p1]:
        return l1[p1]
else:
    return findNth(start,p1-1)

当l2 [p2]大于p1 + p2-1 = n-1个元素时,返回元素l2 [p2](因此是第n个最小的元素).l1 [p1]在相同但对称的条件下返回.如果l1 [p1] <l2 [p2]且l1 [p1 + 1] <l2 [p2],则l2 [p2]的秩大于n,因此我们需要从l1中取更多元素,从l2中取更少.因此,我们在前一个搜索间隔的上半部分中搜索p1.另一方面,如果l2 [p2] <l1 [p1]且l2 [p2 + 1] <l1 [p1],则l1 [p1]的等级大于n.因此,真正的p1将位于我们当前搜索间隔的下半部分.因为我们在每次调用findNth时将问题的大小减半,并且我们只需要做一半的工作来将问题大小减半,这个算法的重现性是T(n)= T(n/2)+ O(1),其具有O(log n) - 时间解.

面试官不断问我上述问题的不同方法.我提出了上述三种方法.这些方法是正确的吗？对于这个问题,还有其他最好的解决办法吗？实际上这个问题问了很多次,所以请提供一些好的东西.

Answer 1

不确定您是否看过这个：http://www.leetcode.com/2011/01/find-k-th-smallest-element-in-union-of.html

这解决了您所询问的问题的更普遍的版本。绝对日志复杂性是可能的......