简介
通常来说,一个算法问题可以有多种解答思路和具体实现,以这样一个问题为例:给定两个数组 int[] nums1
和 int[] nums2
并且我们知道 nums1
和 nums2
都已经排好了序(升序),我们还知道 nums1
有 m
个元素,nums2
有 n
个元素,并且 nums1
的*数组长度*是 m+n
从而足以存储 nums2
中的所有元素,试实现一个算法,它能将 nums2
并入 nums1
,使得算法执行完成后 nums1
数组包含所有原来在 nums1
和 nums2
的元素并且这些元素是呈升序排列的.例如对于输入:
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]
我们希望程序在运行过程中能够*尽量地不额外分配存储空间*,即,尽可能地只在 nums1
和 nums2
所指向的存储空间内进行操作(也叫原地修改,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]
插入在它前方.
插入法的思想非常直接,同时,效率也非常低:nums2
有 n
个元素,也就是说这个插入操作总共要执行 n
次,而 nums1
是数组,执行一块固定长度的内存空间,每当插入一个元素时,例如说在下标 i
的位置插入,那么 nums[i]
,nums[i+1]
,……,nums[m-1]
都得同时往右边”挪动“一步,才能把当前下标 i
的位置”腾挪“出来给要插入的元素 nums[j]
,单次插入的时间复杂度是$O(m)$,总共插入$n$次,总的时间复杂度是$O(m \times n)$,即,平均来说,程序的运行时间基本上正比于$n$和$m$的乘积.如果 nums1
和 nums2
都是大约有$1000$个元素的数组,为了完全插入 nums2
到 nums1
中,这样的”挪动“操作将要进行上百万次.
当然了,因为是原地修改的,没有分配额外存储空间,所有的操作都是在 nums1
和 nums2
已有的存储空间上进行,所以额外需要的空间复杂度应该是$O(1)$,是常数级别的.加上原来程序已经为 nums1
和 nums2
分配好的空间,总的空间复杂度应该是$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)
可以看到,这个版本的实现的提交结果显示运行时为304毫秒,相比之前的376毫秒有明显进步。对了,这个算法的时间复杂度是$O(m+n)$,是线性的,比较次数仅取决于两个数组各自元素个数的最小值,剩下的就是元素的直接复制,而总的空间复杂度是$O(m+n)$,包括在运行时我们额外分配的$O(m+n)$.
我们并不推荐这种做法,因为C#的数组对象是动态分配的,不是在栈上分配的,因为显然我们为 nums3
指定的长度 m+n
是动态的,所以显然不可能在提前在栈上划拨出确定大小的空间给 nums3
,只能是在运行时从堆上分配.而堆上分配的时间开销显然更大.
选择比较法的改进
前面我们实际上违背了题目的限制:只能原地修改 nums1
和 nums2
而不能创建新数组,并且这种做法也给给我们的程序的运行时增加了时间开销(从堆中寻找内存分配给 nums3
)和空间开销(分配给 nums3
的内存),所以现在我们希望可以又不用创建新的数组,又可以使用选择比较法.
我们知道,nums1
有 m
个元素,nums2
有 n
个元素,并且 nums1
的数组长度是 m+n
,多出来 n
个位置是为了能够容纳 nums2
,为了保护程序运行过程中 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)
相比未改进版本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) $$
所以选择比较法是最快的.
我们发现,针对简单的问题,在好奇心的激发下进行思考,也能找出多样化的解决方案.