arrays - 列表的中位数

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

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