5. 合并两个有序数组
88. 合并两个有序数组 - 力扣(LeetCode)
解题思路: 1. 从后往前遍历数组,将nums1和nums2中的元素逐个比较 将较大的元素往nums1末尾进行搬移 2. 第一步结束后,nums2中可能会有数据没有搬移完,将nums2中剩余的元素逐个搬移到nums1 时间复杂度:O(m+n) 空间复杂度: O(1)
void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n){
// end1、end2:分别标记nums1 和 nums2最后一个有效元素位置
// end标记nums1的末尾,因为nums1和nums2中的元素从后往前往nums1中存放
// ,否则会存在数据覆盖
int end1 = m-1;
int end2 = n-1;
int index = m+n-1;
// 从后往前遍历,将num1或者nums2中较大的元素往num1中end位置搬移
// 直到将num1或者num2中有效元素全部搬移完
while(end1 >= 0 && end2 >= 0)
{
if(nums1[end1] > nums2[end2])
{
nums1[index--] = nums1[end1--];
}
else
{
nums1[index--] = nums2[end2--];
}
}
// num2中的元素可能没有搬移完,将剩余的元素继续往nums1中搬移
while(end2 >= 0)
{
nums1[index--] = nums2[end2--];
}
// num1中剩余元素没有搬移完 ---不用管了,因为num1中剩余的元素本来就在num1中
}