88. 合并两个有序数组

题目链接：88. 合并两个有序数组

给你两个有序整数数组 nums1 和 nums2，请你将 nums2 合并到 nums1 中_，_使 nums1 成为一个有序数组。

初始化 nums1 和 nums2 的元素数量分别为 m 和 n 。你可以假设 nums1 的空间大小等于 m + n，这样它就有足够的空间保存来自 nums2 的元素。

示例 1：

输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
输出：[1,2,2,3,5,6]

示例 2：

输入：nums1 = [1], m = 1, nums2 = [], n = 0
输出：[1]

提示：

• nums1.length == m + n
• nums2.length == n
• 0 <= m, n <= 200
• 1 <= m + n <= 200
• -10<sup>9</sup> <= nums1[i], nums2[i] <= 10<sup>9</sup>

思路一：直接排序

将 nums2 赋值到 nums1[m, m+n)，然后进行排序

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

思路二：新建数组（STL使用）

让两个指针分别指向两个数组首地址，并进行比较，较小的值插入到新的数组中

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        vector<int> nums3;
        int i = 0, j = 0;
        while (i < m && j < n) {
            if (nums1[i] <= nums2[j]) {
                nums3.push_back(nums1[i]);
                i++;
            } else if (nums1[i] > nums2[j]) {
                nums3.push_back(nums2[j]);
                j++;
            } 
        }
        if (i == m && j != n) {
            nums3.insert(nums3.end(), nums2.begin()+j, nums2.end());
        }
        if (i != m && j == n) {
            nums3.insert(nums3.end(), nums1.begin()+i, nums1.begin()+m);
        }
        nums1.assign(nums3.begin(), nums3.end());
    }
};

思路三：从后向前赋值

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        int i = m - 1, j = n - 1;
        int tail = m + n - 1;
        while (i > -1 && j > -1) {
            if (nums1[i] >= nums2[j]) {
                nums1[tail--] = nums1[i];
                i--;
            } else if (nums1[i] < nums2[j]) {
                nums1[tail--] = nums2[j];
                j--;
            }
        }
        // 跳出循环后，如果nums2赋值完了，nums1自然有序，所以不用以下判断
        // if (i == -1 && j != -1) {
        //     while (j != -1) {
        //         nums1[tail--] = nums2[j--];
        //     }
        // }
        // if (i != -1 && j == -1) {
        //     while (i != -1) {
        //         nums1[tail--] = nums1[i--];
        //     }
        // }
        while (j != -1) {
            nums1[tail--] = nums2[j--];
        }
    }
};