20240324每日一题题解
Problem
给两个按照非递减顺序排列的整数数组num1和num2，另外有两个整数m和n，分别表示num1和num2中的元素数目。
请合并num2到num1中，使得合并后的数组还是按照非递减顺序排列。
注意，需要将合并之后的数组还是存储在数组num1中。
示例 1:
输入:nums1=[1,2,3,0,0,0]，m=3，nums2=[2,5,6]，n=
3输出:[1,2,2,3,5,6]
Solution
题外话：这道题的输入输出格式对于C++极其不友好。所以为了编写C++的程序，略微将输入输出方式稍加改变，变成输入三行，第一行输入m和n，第二行和第三行分别输入num1和num2两个数组，用空格分隔。
题外话2：今天的题目稍微难，可能涉及到sort()函数。但是学会了就非常好用。
合并+排序
将第二个数组插入到第一个数组的末尾，将第一个数组排序，即完成了两个数组的合并。
关于排序，我们使用头文件algorithm中的sort()函数。
sort(a,b)的用法：
首先，sort 函数的参数是一个范围，表示要对数组中某一段元素进行排序。它接受两个“位置”作为参数，第一个“位置”指向要排序的范围的起始位置，第二个“位置”指向要排序的范围的末尾位置的下一个位置。
“位置”应该如何表达呢？数组的名字就是这个数组的启示位置。就比如说，num表示数组num的第0个位置，也就是num[0]的位置。
如果你要对a[1]...a[n]排序，那么应该写成sort(a+1,a+n+1)。
#include<iostream>// 包含输入输出流头文件
#include<algorithm>// 包含algorithm头文件，用于使用 sort 函数
using namespace std;
int m,n;
int num1[1000],num2[1000];
int main()
{
cin>>m>>n;
// 循环读取 num1 中的元素，将其存储在数组 num1 中
for(int i=1;i<=m;i++)
cin>>num1[i];
// 循环读取 num2 中的元素，将其存储在数组 num2 中
for(int i=1;i<=n;i++)
cin>>num2[i];
// 将 num2 中的元素依次加入到 num1 中，从 m+1 的位置开始加入
for(int i=1;i<=n;i++)
num1[i+m]=num2[1];
// 使用 sort 函数对 num1 数组进行排序，从下标 1 开始，到 n+m 结束
sort(num1+1,num1+n+m+1);
/*
我们希望对 num1 数组中从第二个元素（num1[1]）开始，
到最后一个元素（num1[n + m]）结束的范围进行排序。
所以，我们传递给 sort 函数的第一个参数是 num1 + 1，
表示起始位置是从 num1 数组的第二个元素开始。
而第二个参数是 num1 + n + m + 1，
表示要排序的范围结束于 num1 数组的第 n + m 个元素的下一个位置。
*/
// 输出排序后的 num1 数组中的所有元素
for(int i=1;i<=n+m;i++)
{
cout<<num1[i]<<" ";
}
return 0;
}
双指针+临时数组
注意到原来的两个数组是有序的，我们可以用更快的算法时间复杂度、更巧妙的算法来解决这个问题——双指针法。
双指针法合并两个有序数组的具体做法可以用非常浅显的道理来解释。
想象你有两摞扑克牌，每一摞都是按照从小到大的顺序排列好的。现在你想把这两摞牌合并成一摞，仍然保持从小到大的顺序。
-
你可以放两只手指在每一摞牌的顶端，然后比较两只手指所指的牌的大小。
-
如果其中一只手指所指的牌比较小，你就把这张牌放到新的一摞牌的最上面，然后移动那只手指到下一张牌。
-
反之，如果另一只手指所指的牌比较小，就把这张牌放到新的一摞牌的最上面，然后移动那只手指到下一张牌。
重复这个过程，直到两摞牌都遍历完，就完成了合并。
在这个过程中，两只手指分别对应着两个数组的索引，通过不断地移动手指和比较牌的大小，你可以很自然地将两个有序数组合并成一个有序数组。
#include<iostream>
using namespace std;
int num1[1000],num2[1000];// 声明两个数组 num1 和 num2，用于存储输入的整数序列
int ans[2000];// 声明数组 ans，用于存储合并后的整数序列
int m,n;// 声明变量 m 和 n，分别表示 num1 和 num2 中的元素数目
int main()
{
//读入所有数据
cin>>m>>n;
for(int i=1;i<=m;i++) cin>>num1[i];
for(int i=1;i<=n;i++) cin>>num2[i];
int p1=1,p2=1,p3=1;
// 声明三个整型 p1、p2、p3
// 代表着当前处理到了数组的某个位置
// 用于遍历 num1、num2 和 ans 数组
// 循环合并 num1 和 num2 中的元素，直到其中一个数组遍历完毕
while(p1<=m||p2<=n)
{
// 如果 num1 数组已经遍历完毕，将 num2 中的元素依次加入到 ans 中
if(p1>m)
{
ans[p3]=num2[p2];
p3++;
p2++;
continue;
}
// 如果 num2 数组已经遍历完毕，将 num1 中的元素依次加入到 ans 中
if(p2>n)
{
ans[p3]=num2[p1];
p3++;
p1++;
continue;
}
// 如果 num1[p1] 小于 num2[p2]，说明 num1[p1] 应该在 num2[p2]的前面
if(num1[p1]<num2[p2])
{
ans[p3]=num1[p1];// 将 num1[p1] 加入到 ans 中，并移动 p1 指针
p3++;
p1++;
}
else// 否则，将 num2[p2] 加入到 ans 中，并移动 p2 指针
{
ans[p3]=num2[p2];
p3++;
p2++;
}
}
// 输出合并后的数组 ans
for(int i=1;i<p3;i++)
{
cout<<ans[i]<<" ";
}
return 0;
}