正经题解｜合并有序数组

【算法分析】

将两组数组分别存在 $a$，$b$ 数组中，合并的结果存在 $c$ 数组中。

考虑归并排序中合并的方法，$i$，$j$ 为两个数组的初始位置赋值为 $1$，$cnt$ 初始化为 $0$ 表示 $c$ 数组的初始位置。

while循环条件为：i <= n && j <= m，在循环中：

如果 $a[i]<b[j]$，表示 $a[i]$ 的值在 $b[j]$ 前面，将
$a[i]$ 的值赋给 $c[cnt]$，i++，cnt++，下标加 $1$ 进行下一轮比较。

否则 $b[j]$ 的值在 $a[i]$ 前面，将 $b[j]$ 的值赋给 $c[cnt]$，j++，cnt++，下标加 $1$ 进行下一轮比较。

循环结束后，$a$ 数组和 $b$ 数组中可能存在剩下的元素没有赋值，将剩下的元素存在 $c$ 数组中。

最后输出 $c$ 数组。

【参考代码】

#include <iostream>
using namespace std;

const int N = 1e4 + 10;
int a[N], b[N], c[2*N];

int main() {
	int n, m;
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	for (int i = 1; i <= m; i++) {
		cin >> b[i];
	}
	//合并 
	int i = 1, j = 1;
	int cnt = 0;
	while(i <= n && j <= m){
		if(a[i] <= b[j]){
			c[cnt] = a[i];
			cnt++;
			i++;  
			//c[cnt++] = a[i++];
		}else {
			c[cnt] = b[j];
			cnt++;
			j++;
			//c[cnt++] = b[j++];
		}
	}
	// 如果 b 结束了，a还剩元素 
	while(i <= n) c[cnt++] = a[i++];
	// 如果 a 结束了，b还剩元素 
	while(j <= m) c[cnt++] = b[j++];
	for(int i = 0; i < cnt; i++){
		cout << c[i] << " ";
	}
	return 0;
}

【时间复杂度】

$O(n+m)$

【预计得分】

$100pts$