合并两个有序数组

题目描述

  给定两个有序数组，把两个数组合并为一个

输入输出样例

  输入是两个数组和它们分别的长度m和m。其中第一个数组的长度被延长至m+n，多出的n位被0填补。题目要求把第二个数组归并到第一个数组上，不需要开辟额外空间。

Input: nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
Output: nums1 = [1,2,2,3,5,6]

# 题解   因为这两个已经排好序，我们可以把两个指针分别放在两个数组的末尾，即nums1的m-1位和nums2的n-1位，每次将较大的那个数字复制到nums1的后边，然后向前移动一位。因为我们也要定位nums1的末尾，所以我们还需要第三个指针，以便复制。   在以下的代码里，我们直接利用m和n当作两个数组的指针，再额外创立一个pos指针，起始位置为m+n-1。每次向前移动m或n的时候，也要向前移动pos。这里需要注意，如果nums1的数字已经复制完，不要忘记把nums2的数字继续复制；如果nums2的数字已经复制完，剩余nums1的数字不需要改变，因为它们已经被排好序。

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        int i = m - 1, j = n - 1, pos = m + n - 1;
        
        while (i >= 0 && j >= 0) {
            if (nums1[i] > nums2[j])
                nums1[pos--] = nums1[i--];
            else 
                nums1[pos--] = nums2[j--];
        }
        
        while (j >= 0)
            nums1[pos--] = nums2[j--];
    }
};