arrays - 两个数组中第 k 个最小的数，一个已排序，另一个未排序

Question

已经有一个 answer对于两个排序数组。但是，在我的问题中，其中一个数组是未排序的。

假设 X[1..n]和 Y[1..m]其中 n < m . X 已排序，Y 未排序。找到 X U Y 的第 k 个最小数的有效算法是什么？ .

MinHeap 可用于查找未排序数组中第 k 个最小的数字。但是，这里对这些数组之一进行了排序。我能想到:

 1. Building a `MinHeap` for `Y`
 2. i = 1, j = 1
 3. x1 = extract Min from Y
 4. x2 = X[i]; 
 5. if j == k: return min(x1, x2)
 5. if x1 < x2: j++; goto 3
 6. else: j++; i++; goto 4 

它是否有效且正确？

Answer 1

没有帮助，但你必须扫描 Y .这需要 O(m)所以你不能比O(m)做得更好.

但是quickselect表现一般O(m) .基本上，该算法只是进行快速排序，除了您忽略所有没有最终答案的分区。

鉴于n < m我们可以简单地将一个数组连接到另一个数组并进行快速选择。

请注意，平均性能不错，但最坏情况下的性能是二次方的。要解决这个问题，如果你没有足够快地取得进展，你可以切换到相同的中位数算法，该算法提供快速排序保证性能(尽管有错误的常量)。如果您不熟悉它，那就是将数组分成 5 组，找到每组的中位数，然后重复直到只剩下 1 个元素。然后将该元素用作整个数组的基准。