合并两个已排序数组的几种方法

2020-08-22

简介

通常来说,一个算法问题可以有多种解答思路和具体实现,以这样一个问题为例:给定两个数组 int[] nums1int[] nums2 并且我们知道 nums1nums2 都已经排好了序(升序),我们还知道 nums1m 个元素,nums2n 个元素,并且 nums1数组长度m+n 从而足以存储 nums2 中的所有元素,试实现一个算法,它能将 nums2 并入 nums1,使得算法执行完成后 nums1 数组包含所有原来在 nums1nums2 的元素并且这些元素是呈升序排列的.例如对于输入:

nums1 = [1, 6, 7, 10, 11, 0, 0, 0, 0]
nums2 = [2, 8, 9, 12]
m = 5
n = 4

我们实现的算法执行完毕后 nums1 应当变为

nums1 = [1, 2, 6, 7, 8, 9, 10, 11, 12]

我们希望程序在运行过程中能够尽量地不额外分配存储空间,即,尽可能地只在 nums1nums2 所指向的存储空间内进行操作(也叫原地修改,in place).

插入法

题目给出的某些提示或者限制其实也很有可能会对我们造成误导,并且影响我们的正常发挥.拿这题为例,我们看到 nums1长度n+m,我们就会首先想通过原地修改(in place)来实现,插入法(Insertion)主要就是找到合适的位置,把占用位置的元素往右挪一步,然后把要插入的元素放入数组某个位置,这也是很容易想出的一个方法,我们来看一下这个算法具体是怎么样的吧.

首先,对于 nums2 中的每个元素 nums[j],设当前我们为 nums1 维护的指针为 i,而 j 是我们为 nums2 维护的指针,我们比较 nums2[j]nums1[i],如果 nums2[j] 小于等于 nums1[i],那就插入,否则 i 自增 1,主要的思想就是,对于 nums1 中的每个元素 nums1[i],我们都企图在 nums2 中找到所有比它小的 nums2[j] 插入在它前方.

插入法的思想非常直接,同时,效率也非常低:nums2n 个元素,也就是说这个插入操作总共要执行 n 次,而 nums1 是数组,执行一块固定长度的内存空间,每当插入一个元素时,例如说在下标 i 的位置插入,那么 nums[i]nums[i+1],……,nums[m-1]都得同时往右边”挪动“一步,才能把当前下标 i 的位置”腾挪“出来给要插入的元素 nums[j],单次插入的时间复杂度是$O(m)$,总共插入$n$次,总的时间复杂度是$O(m \times n)$,即,平均来说,程序的运行时间基本上正比于$n$和$m$的乘积.如果 nums1nums2 都是大约有$1000$个元素的数组,为了完全插入 nums2nums1 中,这样的”挪动“操作将要进行上百万次.

当然了,因为是原地修改的,没有分配额外存储空间,所有的操作都是在 nums1nums2 已有的存储空间上进行,所以额外需要的空间复杂度应该是$O(1)$,是常数级别的.加上原来程序已经为 nums1nums2 分配好的空间,总的空间复杂度应该是$O(m+n)$.

以C#语言为例,实现如下:

public static void ShiftRight(int[] nums, int startIndex) {
    if (nums.Length == 1 || nums.Length == 0 || startIndex == nums.Length-1) {
        return;
    }

    for (var i = nums.Length-2; i >= startIndex; i--) {
        nums[i+1] = nums[i];
    }
}

public static void InsertAt(int[] nums, int startIndex, int x) {
    Utilities.ShiftRight(nums, startIndex);
    nums[startIndex] = x;
}

public static void MergeByInsert(int[] nums1, int m, int[] nums2, int n)
{
    if (nums1.Length == 0 || nums2.Length == 0) {
        return;
    }

    if (nums1.Length != m+n || nums2.Length != n) {
        Console.WriteLine("Incorrect parameters: ");
        Console.WriteLine($"nums1.Length: {nums1.Length}, m: {m}, nums2.Length: {nums2.Length}, n: {n}");
        return;
    }

    int i = 0;
    int j = 0;
    int k = m;
    while (i <= k-1 && j <= n-1) {
        if (nums2[j] <= nums1[i]) {
            Utilities.InsertAt(nums1, i, nums2[j]);
            j = j + 1;
            k = k + 1;
        }

        i = i + 1;
    }
    
    while (k <= nums1.Length-1) {
        nums1[k] = nums2[j];
        k = k + 1;
        j = j + 1;
    }
}

注意由于是C#语言所以我们省去了一些繁琐的部分只保留了主要逻辑,以下是运行结果:

运行截图:插入法

运行截图:插入法

后面会看到这个实现(或者说这种算法)是比较慢的.

选择比较法

不妨先暂时忘掉”原地修改“的这个限制,我们考虑一种更加直观的方法,事实将会证明:这种方法也更快.类比于我们在纸上手工计算两个有序数组的合并,每一次,我们可以从两个数组中选出一个最小的,然后把那个最小的记下来,并在原数组上划掉,这样最终我们会得到一个数组,这个数组同时包含原来两个数组的所有元素并且也是升序的.伪代码如下:

int[] nums3 = new int[m+n]

int j = 0
int k = 0
for (var i = 0; i < m+n; i++) {
    if nums1[j] <= nums2[k] {
        nums3.push(nums1[j])
        j = j + 1
    }
    else {
        nums3.push(nums2[k])
        k = k + 1
    }
    i = i + 1
}

为了看似满足题目的要求——不返还任何值,我们最终将 nums3 也就是这个新创建的临时数组的值复制到 nums1 即可,下面是较为完整的C#实现:

public static void MergeByCompareV1(int[] nums1, int m, int[] nums2, int n) {

    if (nums1.Length == 0 || nums2.Length == 0) {
        return;
    }

    if (nums1.Length != m+n || nums2.Length != n) {
        Console.WriteLine("Incorrect parameters: ");
        Console.WriteLine($"nums1.Length: {nums1.Length}, m: {m}, nums2.Length: {nums2.Length}, n: {n}");
        return;
    }

    int[] nums3 = new int[m+n];
    int i = 0;
    int j = 0;
    int k = 0;
    while (i <= m-1 && j <= n-1) {
        if (nums1[i] <= nums2[j]) {
            nums3[k] = nums1[i];
            i = i + 1;
        }
        else {
            nums3[k] = nums2[j];
            j = j + 1;
        }
        k = k + 1;
    }

    while (j <= n-1) {
        nums3[k] = nums2[j];
        j = j + 1;
        k = k + 1;
    }

    while (i <= m-1) {
        nums3[k] = nums1[i];
        i = i + 1;
        k = k + 1;
    }

    int l = 0;
    while (l <= m+n-1) {
        nums1[l] = nums3[l];
        l = l + 1;
    }
}

其中第一段 while 是比较和选择,第二段和第三段 while 将只有一段被真正执行——是为了将之前没有被选中的元素追加到 nums3 中,而最后一段 while 是将 nums3 复制到 nums2

运行截图:选择比较法(1)

运行截图:选择比较法(1)

可以看到,这个版本的实现的提交结果显示运行时为304毫秒,相比之前的376毫秒有明显进步。对了,这个算法的时间复杂度是$O(m+n)$,是线性的,比较次数仅取决于两个数组各自元素个数的最小值,剩下的就是元素的直接复制,而总的空间复杂度是$O(m+n)$,包括在运行时我们额外分配的$O(m+n)$.

我们并不推荐这种做法,因为C#的数组对象是动态分配的,不是在栈上分配的,因为显然我们为 nums3 指定的长度 m+n 是动态的,所以显然不可能在提前在栈上划拨出确定大小的空间给 nums3,只能是在运行时从堆上分配.而堆上分配的时间开销显然更大.

选择比较法的改进

前面我们实际上违背了题目的限制:只能原地修改 nums1nums2 而不能创建新数组,并且这种做法也给给我们的程序的运行时增加了时间开销(从堆中寻找内存分配给 nums3)和空间开销(分配给 nums3 的内存),所以现在我们希望可以又不用创建新的数组,又可以使用选择比较法.

我们知道,nums1m 个元素,nums2n 个元素,并且 nums1 的数组长度是 m+n,多出来 n 个位置是为了能够容纳 nums2,为了保护程序运行过程中 nums1 的元素不被覆写,我们只需将 nums1 的元素往右移到尽头就可以了:

挪动 nums1 中的元素

挪动 nums1 中的元素

nums1 的所有元素一次性往右边移动 n 步(是为了移到尾端)的时间复杂度是$O(m)$:

for (var i = 0; i < m; i++) {
    nums1[n+m-1-i] = nums1[n+m-1-i-n];
}

移动之后,就可以像之前的选择比较法那样进行操作了,只不过这时 nums1 的第一个元素的下标变成了 n,并且 min(nums[i], nums[j]) 不需要再向 nums3 写入,而是可以直接向 nums1 写入,这样并不会影响到 nums1 已有的元素,因为它们都已经被提前移到尾端了:

public static void MergeByCompareV2(int[] nums1, int m, int[] nums2, int n) {

    if (nums1.Length == 0 || nums2.Length == 0) {
        return;
    }

    if (nums1.Length != m+n || nums2.Length != n) {
        Console.WriteLine("Incorrect parameters: ");
        Console.WriteLine($"nums1.Length: {nums1.Length}, m: {m}, nums2.Length: {nums2.Length}, n: {n}");
        return;
    }

    for (var i = 0; i < m; i++) {
        nums1[n+m-1-i] = nums1[n+m-1-i-n];
    }

    int j = 0;
    int k = n;
    int l = 0;
    while (m !=0 && n != 0) {
        if (nums1[k] <= nums2[l]) {
            nums1[j] = nums1[k];
            k = k + 1;
            m = m - 1;
        }
        else {
            nums1[j] = nums2[l];
            l = l + 1;
            n = n - 1;
        }
        j = j + 1;
    }

    while (m != 0) {
        nums1[j] = nums1[k];
        k = k + 1;
        j = j + 1;
        m = m - 1;
    }

    while (n != 0) {
        nums1[j] = nums2[l];
        l = l + 1;
        j = j + 1;
        n = n - 1;
    }
}

第一段 for 循环是移动 nums1 中的所有元素到尾端,而第一段 while 循环所做的是比较和选择,把较小的元素写入到 nums1 中,而最后两段 while 循环将只有其中一段被执行,是为了把未被选上的元素追加到 nums1 中.运行结果:

运行结果:选择比较法(2)

运行结果:选择比较法(2)

相比未改进版本304毫秒这次进步了64毫秒,还是有些明显的.总的时间复杂度和空间复杂度与前面的一致.

连接排序法

最后一种方法较为简单,首先将 nums2 的元素追加到 nums1 的元素的尾端,然后调用C#运行时自动加载的排序方法排序:

public static void MergeByConcatAndSort(int[] nums1, int m, int[] nums2, int n) {

    int j = 0;
    for (var i = m; i < m+n; i++) {
        nums1[i] = nums2[j];
        j = j + 1;
    }

    Array.Sort(nums1);
}

运行效果并不是最快的:

运行结果:连接排序法

运行结果:连接排序法

但相比插入法和未经过改进的选择比较法都更快.这种方法事实上也是可行的,因为语言标准库/运行时提供的排序方法的实现都是很高效的.假如说用的是快速排序方法作为实现,那么总的时间复杂度将会是$O(n\times \mathop{log}n)$,其中假设$n \geq m$,而空间复杂度是$O(n+m)$.可以认为$O(n \times \mathop{log}n)$是比$O(m+n)$慢的,假设$m$和$n$都大约同为$1000$,那么$n\mathop{log}n \approx n \mathop{log} 1000 \approx 3 n$,而 $m+n \leq 2n, n \geq m$.

总结

我们先后介绍了三种方法用于解决两个有序数组的合并问题,分别是插入法,选择比较法,和连接排序法,插入法的时间复杂度是$O(nm)$近似为$O(n^2)$(假设$n$大于或等于$m$),而选择比较法的时间复杂度是$O(m+n)$可以看做是$O(n)$(假设$n$大于或等于$m$),连接排序法的时间复杂度是$O(n \mathop{log}n)$,一般来说,我们认为

$$ O(n^2) \geq O(n \mathop{log}n) \geq O(n) $$

所以选择比较法是最快的.

我们发现,针对简单的问题,在好奇心的激发下进行思考,也能找出多样化的解决方案.

学习记录algorithmleetcodearray

通过问题转化巧解 Maximum Subarray 问题

Longest Common Prefix 问题基于 N-ary Tree 的解法