【力扣每日一题】2023.8.13 合并两个有序数组

目录

题目：

示例：

分析：

代码：

---

题目：

示例：

分析：

题目给我们两个升序数组，让我们合并它们，要求合并之后仍然是升序，并且这个合并操作是在数组1原地修改的。数组1的有效数据长度为 m ，而数组1的长度为 m + n，n 是数组2的有效数据长度以及数组的长度。

比较直观容易想到的做法就是先把数组1的尾部删去 n 个无效数据，再把数组2都添加到数组1的尾部。接着直接对数组1排序即可。这样做是可以的，效果也还不错。

 不过这么做就没有利用到原数组是升序的这样一个特性。

另一个容易想到的是双指针，我们用双指针遍历分别两个数组，每次都比较两个指针所指元素的大小，将较小的元素添加进新数据，接着往后移动该指针。直到两个指针的大小分别为 m 和 n 即为遍历结束。

最后将新数组赋值给数组1即可。

那这么做还是有点不痛快，还是直接在数组1原地修改比较舒服。那有没有办法呢？

答案是有的。

首先我们上述办法肯定是不行的，这么做会把数组1的有效数据覆盖掉，那应该怎么做呢。

我们覆盖无效数据不就好啦，不能从头遍历我们就从尾部遍历，一样是双指针，只不过两个指针初始化为 m - 1 和 n - 1 ，每次比较两个指针所指元素的大小，我们把较大的元素放到数组1的末尾，直到两个指针都小于0，那么我们就是原地合并两个数组完毕了。

代码：

class Solution {
public:void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {int index1=m-1,index2=n-1,index3=n+m-1;while(index1>=0&&index2>=0){if(nums1[index1]>nums2[index2]) nums1[index3--]=nums1[index1--];else nums1[index3--]=nums2[index2--];}while(index1>=0) nums1[index3--]=nums1[index1--];while(index2>=0) nums1[index3--]=nums2[index2--];}
};