合并升序数组

问题

要找到 $n$ 个数组的第 $k$ 大。

解法

多指针

用一个堆维护每个数组的差分，每次选取差分最小的进行操作。总时间是 $O(k\log n)$。

minmax 卷积

和多指针相同，只不过是双指针。合并两个数组的时间是 $O(k)$。总时间是 $O(nk)$。如果需要知道数组集合的一些子集的合并结果，这个方法比多指针快。