【力扣每日一题】2023.8.13 合并两个有序数组-Toy模板网

这篇具有很好参考价值的文章主要介绍了【力扣每日一题】2023.8.13 合并两个有序数组。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

题目：

示例：

分析：

代码：

题目：

【力扣每日一题】2023.8.13 合并两个有序数组,力扣每日一题,leetcode,算法,c++,数据结构

示例：

【力扣每日一题】2023.8.13 合并两个有序数组,力扣每日一题,leetcode,算法,c++,数据结构

分析：

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

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

【力扣每日一题】2023.8.13 合并两个有序数组,力扣每日一题,leetcode,算法,c++,数据结构

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

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

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

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

答案是有的。

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

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

【力扣每日一题】2023.8.13 合并两个有序数组,力扣每日一题,leetcode,算法,c++,数据结构文章来源地址https://www.toymoban.com/news/detail-651196.html

代码：

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--];
    }
};

到了这里，关于【力扣每日一题】2023.8.13 合并两个有序数组的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！