力扣88、合并两个有序数组

思路

• 思路一：直接合并，合并后排序、
• 思路二：双指针，从数组一最后元素开始找到合适数组二从头先插入元素的位置

代码：思路一

class Solution {
public:
    void merge(vector& nums1, int m, vector& nums2, int n) {
        for (int i = m, j = 0; i < n + m && j < n; i++, j++) {
            nums1[i] = nums2[j];
        }
        sort(nums1.begin(), nums1.end());
    }
};

代码：思路二

版本一

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n){
    for (int i = 0; i < n; i++) {
        int j = m - 1;
        while (j >= 0 && nums2[i] < nums1[j]) nums1[j + 1] = nums1[j], --j; //找到nums2[i]插入的位置
        nums1[j + 1] = nums2[i];
        m++;
    }
}

版本二

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n){
    for (int i = n - 1; i >= 0; i--) {
        int j = m - 1;
        while (j >= 0 && nums2[i] < nums1[j]) nums1[j + 1] = nums1[j], --j;
        nums1[j + 1] = nums2[i];
        m++;
    }
}