网站建设哪家好推荐万维科技,做一个网站分析应该怎么做,免费聊天网站模板和源码,wordpress中文网站优化目录
题目#xff1a;
示例#xff1a;
分析#xff1a;
代码#xff1a; 题目#xff1a; 示例#xff1a; 分析#xff1a;
题目给我们两个升序数组#xff0c;让我们合并它们#xff0c;要求合并之后仍然是升序#xff0c;并且这个合并操作是在数组1原地修改…目录
题目
示例
分析
代码 题目 示例 分析
题目给我们两个升序数组让我们合并它们要求合并之后仍然是升序并且这个合并操作是在数组1原地修改的。数组1的有效数据长度为 m 而数组1的长度为 m nn 是数组2的有效数据长度以及数组的长度。
比较直观容易想到的做法就是先把数组1的尾部删去 n 个无效数据再把数组2都添加到数组1的尾部。接着直接对数组1排序即可。这样做是可以的效果也还不错。 不过这么做就没有利用到原数组是升序的这样一个特性。
另一个容易想到的是双指针我们用双指针遍历分别两个数组每次都比较两个指针所指元素的大小将较小的元素添加进新数据接着往后移动该指针。直到两个指针的大小分别为 m 和 n 即为遍历结束。
最后将新数组赋值给数组1即可。
那这么做还是有点不痛快还是直接在数组1原地修改比较舒服。那有没有办法呢
答案是有的。
首先我们上述办法肯定是不行的这么做会把数组1的有效数据覆盖掉那应该怎么做呢。
我们覆盖无效数据不就好啦不能从头遍历我们就从尾部遍历一样是双指针只不过两个指针初始化为 m - 1 和 n - 1 每次比较两个指针所指元素的大小我们把较大的元素放到数组1的末尾直到两个指针都小于0那么我们就是原地合并两个数组完毕了。 代码
class Solution {
public:void merge(vectorint nums1, int m, vectorint nums2, int n) {int index1m-1,index2n-1,index3nm-1;while(index10index20){if(nums1[index1]nums2[index2]) nums1[index3--]nums1[index1--];else nums1[index3--]nums2[index2--];}while(index10) nums1[index3--]nums1[index1--];while(index20) nums1[index3--]nums2[index2--];}
};
