C/C++每日一练：合并两个有序数组
题目要求
给定两个已经排好序（从小到大）的数组 arr1 和 arr2，将它们合并为一个新的有序数组，并返回结果。要求最终的数组仍然是从小到大排序的，且不使用额外的排序函数。
输入：两个升序排序的数组 arr1 和 arr2 ，长度分别为 m 和 n。
输出：一个包含所有元素并且升序排序的新数组。
示例：
输入：arr1 = {1, 3, 5}, arr2 = {2, 4, 6}
输出：{1, 2, 3, 4, 5, 6}
思路解析
- 双指针法：由于两个数组都是有序的，可利用双指针同时遍历两个数组，逐个比较当前指针指向的元素，把较小的元素插入结果数组，再更新指针。
- 边界条件处理：当一个数组遍历完后，直接将另一个数组剩余的元素添加到结果数组的末尾。
- 时间复杂度：每个数组的元素只被遍历一次，所以时间复杂度为 O(m + n)。
过程解析
- 设定两个指针 i 和 j，分别指向 arr1 和 arr2 的开头（也可以指向末尾）。
- 比较 arr1[i] 和 arr2[j]，较小的元素加入新数组，并移动相应的指针，需要注意的是这里移动的指针是指向较小数据的那一个数组元素的指针。
- 当其中一个数组遍历完毕时，直接将另一个数组的剩余元素加入新数组。
运用到的知识点
- 数组遍历：通过下标进行数组元素访问。
- 双指针技巧：在两个有序集合上应用双指针能够实现高效的合并。
- 动态内存分配：为新数组分配足够的内存存储结果（在C语言中）。
- 条件判断：对比两个指针指向的元素并决定移动哪个指针。
示例代码
C实现
#include <stdio.h> // 引入标准输入输出库，用于printf函数
#include <stdlib.h> // 引入标准库，用于malloc和free函数
// 合并两个有序数组的函数声明
int* mergeSortedArrays(int arr1[], int m, int arr2[], int n) {
int* result = (int*)malloc((m + n) * sizeof(int)); // 动态分配一个足够大的数组来存储合并后的结果，大小为两个数组长度之和
int i = 0, j = 0, k = 0; // 初始化三个索引变量i, j, k，分别用于遍历arr1, arr2和结果数组
// 使用while循环遍历两个数组，依次比较元素大小，将较小的元素加入结果数组
while (i < m && j < n) { // 当两个数组都还有未遍历的元素时
if (arr1[i] < arr2[j]) { // 如果arr1当前元素小于arr2当前元素
result[k++] = arr1[i++]; // 将arr1当前元素加入结果数组，并移动arr1的索引
}
else { // 否则
result[k++] = arr2[j++]; // 将arr2当前元素加入结果数组，并移动arr2的索引
}
}
// 处理剩余的元素，如果有的话，将它们加入到结果数组
while (i < m) { // 如果arr1还有未遍历的元素
result[k++] = arr1[i++]; // 将它们逐个加入到结果数组
}
while (j < n) { // 如果arr2还有未遍历的元素
result[k++] = arr2[j++]; // 将它们逐个加入到结果数组
}
return result; // 返回合并后的数组指针
}
// 打印数组的函数声明
void printfArray(int* arr,int size);
int main()
{
int arr1[] = { 1, 3, 5 }; // 初始化第一个有序数组
int arr2[] = { 2, 4, 6, 8, 11 }; // 初始化第二个有序数组
int m = sizeof(arr1) / sizeof(arr1[0]); // 计算第一个数组的长度
int n = sizeof(arr2) / sizeof(arr2[0]); // 计算第二个数组的长度
// 调用合并函数，得到合并后的数组指针
int* mergedArray = mergeSortedArrays(arr1, m, arr2, n);
// 打印合并后的数组
printfArray(mergedArray,m+n);
// 释放动态分配的内存，防止内存泄漏
free(mergedArray);
return 0; // 程序正常结束
}
void printfArray(int* arr,int size)
{
printf("Merged Array: ");
for (int i = 0; i < size; i++) { // 遍历合并后的数组
printf("%d ", arr[i]); // 打印每个元素
}
printf("\n"); // 换行
}C++ 实现
#include <iostream> // 引入输入输出流库，用于输入输出操作
#include <vector> // 引入向量容器库，用于存储动态数组
using namespace std; // 使用标准命名空间，简化代码中的std::前缀
// 合并两个有序数组的函数声明
vector<int> mergeSortedArrays(vector<int>& arr1, vector<int>& arr2) {
vector<int> result; // 创建一个空的向量result，用于存储合并后的数组
int i = 0, j = 0; // 初始化两个索引i和j，分别用于遍历arr1和arr2
// 使用while循环遍历两个数组，只要两个数组都还有元素未遍历
while (i < arr1.size() && j < arr2.size()) {
// 比较当前索引下的两个元素，将较小的元素加入result，并移动对应索引
if (arr1[i] < arr2[j]) {
result.push_back(arr1[i++]); // 将arr1当前元素加入result，并将i后移
}
else {
result.push_back(arr2[j++]); // 将arr2当前元素加入result，并将j后移
}
}
// 处理第一个数组arr1中剩余的元素（如果有）
while (i < arr1.size()) {
result.push_back(arr1[i++]); // 将arr1剩余元素依次加入result，并将i后移
}
// 处理第二个数组arr2中剩余的元素（如果有）
while (j < arr2.size()) {
result.push_back(arr2[j++]); // 将arr2剩余元素依次加入result，并将j后移
}
return result; // 返回合并后的数组result
}
// 打印数组的函数声明
void printfArray(vector<int>& arr);
int main()
{
vector<int> arr1 = { 1, 3, 5 }; // 初始化第一个有序数组arr1
vector<int> arr2 = { 2, 4, 6, 8, 11 }; // 初始化第二个有序数组arr2
// 调用合并函数，将arr1和arr2合并为一个新的有序数组mergedArray
vector<int> mergedArray = mergeSortedArrays(arr1, arr2);
// 打印合并后的数组mergedArray
printfArray(mergedArray);
return 0; // 程序正常结束，返回0
}
void printfArray(vector<int>& arr)
{
cout << "Merged Array: ";
for (int num : arr) { // 遍历合并后的数组
cout << num << " "; // 打印每个元素
}
cout << endl; // 换行
}