数组相关面试题

数组相关面试题

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中
}