题目
给出两个有序的整数数组A和B,请将数组B合并到数组A中,变成一个有序的数组。
可以假设A数组有足够的空间存放B数组的元素,A和B中初始的元素数目分别为m和n。
常规方法 (常规的归并排序)
1.思路
- 开辟一个新的空间,用来存储最后的结果,命名为中间数组
- 同时遍历两个数组,用一个中间值存储对比后的数值,比较完成后,存储到中间数组
- 将中间数组拷贝到A数组,完成本题
可以参考归并排序的标准说法:
- 申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列
- 设定两个指针,最初位置分别为两个已经排序序列的起始位置
- 比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置
- 重复步骤3直到某一指针超出序列尾,将另一序列剩下的所有元素直接复制到合并序列尾
这就是一个归并排序的做法
2.代码
class Solution { public: void merge(int A[], int m, int B[], int n) { // A有足够空间存储B数组元素 // 使用一个中间值比较元素值 if (m == 0) { std::copy(B, B+n, A); return ; }javascript:void(0); if (n == 0) { return ; } auto &a_arr = A; auto &b_arr = B; int res_arr[m+n]; int a_index{0}, b_index{0}, res_index{0}; while (a_index != m || b_index != n) { int tmp{0}; int a_num = a_arr[a_index], b_num = b_arr[b_index]; if (a_num < b_num) {javascript:void(0); tmp = a_num; if(a_index == m && b_index != n) { tmp = b_num; ++b_index; } if (a_index != m) { ++a_index; } } else { tmp = b_num; if (b_index == n && a_index != m) { tmp = a_num; ++a_index; } if (b_index != n) { ++b_index; } } res_arr[res_index++] = tmp; } std::copy(res_arr, res_arr+m+n, A); } };
- 小结
该方法很容易想到,和之前的连接两个有序链表思路是一个样子的。当然后续的方法也是一致的,只是把链表换成了数组,数据载体不一样了。
而相对应的,这种方法容易理解而且能满足题目要求,可以直接使用。接下来说明以下其他方法。
不申请新空间的“归并排序”
从后往前处理,会发现不需要申请新的空间。
再简化一下思路,代码写出来会十分简单。
1. 思路
- 直接使用数组
A
作为结果空间(题目说明了A
足够大); - 遍历两者,存入大的数字
- 最终结果
2. 代码
class Solution { public: void merge(int A[], int m, int B[], int n) { // A有足够空间存储B数组元素 // 索引 int a_index{m-1}, b_index{n-1}; int res_index{m+n-1}; while (a_index >= 0 && b_index >= 0) { if (A[a_index] > B[b_index]) { A[res_index] = A[a_index]; --a_index; } else { A[res_index] = B[b_index]; --b_index; } --res_index; } while (b_index >= 0) { A[res_index] = B[b_index]; --res_index; --b_index; } } };
3. 小结
对比一下两者思路是一致的,代码实现有所区别,对比运行的时间是无差别的,内存占用却更多一些(疑惑点)。
第二个while
不好理解。当其中一个数组完成遍历之后,剩余的数据就是有序了。比如下列数据:
先完成B
遍历
A: 1 2 3 4 5 B: 2 3 4 # 一循环之后 B已经遍历完成 A: 1 2 2 3 3 4 4 5 B: 2 3 4
B
未完成遍历
A: 2 2 3 4 5 B: 1 2 # 一循环之后 A: 2 2 2 2 3 4 5 B: 1 2 # 进入二循环 A: 1 2 2 2 3 4 5 B: 1 2
类似例子可以自己尝试手动推导一下。
而本题最重要的是归并的使用,常规方法才是解决实际问题的关键,而思路一致也有代码不同的可能。
其他方法
也可以参考链表的合并,对于链表使用next
作为下一步,此处可以尝试使用全局变量设定index
代替。此处不表。
2020-10-25