algorithm - 将 K 个元素插入到 O(klogk+n) 中的 N 个元素的排序列表中

Question

我们如何在时间 O(k log k + n) 内将 k 个新元素插入到大小为 n 的排序列表中？

我猜 klogk 可以通过首先对 k 个元素进行合并排序然后将它们插入到大小为 n 的列表中来获得。但我缺少 (+n) 部分。

Answer 1

我们可以先对要插入的元素进行排序，这可以通过合并排序或堆排序等算法来完成，在 O(k log k) 中。

接下来我们可以合并这两个列表(或任何类型的数据结构，只要我们可以按升序对其进行迭代)。这种合并可以在 O(k+n) 中完成，因为我们可以同时迭代两个列表，并且每次“发出”两个列表中的最小值并推进相应的游标。

例如，对于两个已排序的数组，我们可以将它们合并为:

public static int[] merge_sorted(int[] a, int[] b) {
    k = a.length;
    n = b.length;
    int[] c = new int[k+n];
    int ai = 0;
    int bi = 0;
    int ci = 0;
    while(ai < k && bi < n) {
        if(a[ai] <= b[bi]) {
            c[ci++] = a[ai++];
        } else {
            c[ci++] = b[bi++];
        }
    }
    while(ai < k) {
        c[ci++] = a[ai++];
    }
    while(bi < n) {
        c[ci++] = b[bi++];
    }
    return c;
}

所以时间复杂度是O(k log k + k + n)，但这等于O(k log k + n)。