LeetCode_88合并两个有序数组
目录
【LeetCode_88】合并两个有序数组
LeetCode第88题：合并两个有序数组
github地址
前言
本文使用C++实现LeetCode第88题
题目描述
题目链接：
题目与思路分析
目标分析：
- 将两个非递减数组
nums1和nums2中的数据合并到nums1中 - 合并后的数组保持非递减顺序
- 不复制数组，即原地合并，意味着时间复杂度为
O(n)，空间复杂度为O(1) - 直接对原数组进行操作，直接合并到
nums1中
思路：双指针：两个指针从后往前操作，依次比较两个数组中末尾元素的大小，将较大者放在nums1的末尾。比较结束后再进行剩余元素的处理
end1：指向nums1中最后一个有效元素的位置，初始下标为m - 1end2：指向nums2中最后一个有效元素的位置，初始下标为n - 1dst：指向较大元素应该被放入的位置，初始下标为nums1.size() - 1
操作：
- 循环比较移动数据，end1和end2只要有一个下标结束循环就结束，循环继续的条件为
end1 >= 0 && end2 >= 0 - 比较元素：
nums1[end1] >= nums2[end2]时：将较大元素nums1[end1]放在nums1[dst]，同时dst和end1各减减nums1[end1] < nums2[end2]时：将较大元素nums2[end2]放在nums1[dst]，同时dst和end2各减减
- 循环结束后，只可能有两种情况：
end2先结束：此时nums1中的数据直接就为有序的，无需任何操作end1先结束：说明此时nums2中还有数据未合并到nums1中，需要手动合并
代码实现
class Solution {
public:
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
int end1 = m - 1, end2 = n - 1;
int dst = nums1.size() - 1;
// 只要有一个结束就结束
while(end1 >= 0 && end2 >= 0){
if(nums1[end1] >= nums2[end2]){
nums1[dst] = nums1[end1];
dst--;
end1--;
}
else{
nums1[dst] = nums2[end2];
dst--;
end2--;
}
}
// end2 先结束不用管，end1先结束时，需要把nums2中的数据再拷贝过来
while(end2 >= 0){
nums1[dst] = nums2[end2];
dst--;
end2--;
}
}
};算法代码优化
- 利用后置
--优化代码
class Solution {
public:
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
int end1 = m - 1, end2 = n - 1;
int dst = nums1.size() - 1;
// 只要有一个结束就结束
while(end1 >= 0 && end2 >= 0){
if(nums1[end1] >= nums2[end2])
nums1[dst--] = nums1[end1--];
else
nums1[dst--] = nums2[end2--];
}
// end2 先结束不用管，end1先结束时，end2还未结束，需要把nums2中的数据再拷贝过来
while(end2 >= 0)
nums1[dst--] = nums2[end2--];
}
};以上就是本文的所有内容了，如果觉得文章对你有帮助，欢迎 点赞⭐收藏 支持！如有疑问或建议，请在评论区留言交流，我们一起进步
分享到此结束啦一键三连，好运连连！你的每一次互动，都是对作者最大的鼓励！
征程尚未结束，让我们在广阔的世界里继续前行！🚀