Leetcode 88：合并两个有序数组

• 题目描述
• 我的解法
• 其它解法1：直接赋值，不用push_back
• 其它解法2：对解法1的简化
• 其它解法3-5：用到vector自带的api

题目描述

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

说明:

• 初始化 nums1 和 nums2 的元素数量分别为 m 和 n 。
• 你可以假设 nums1 有足够的空间（空间大小大于或等于 m + n）来保存 nums2 中的元素。

示例：

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

输出: [1,2,2,3,5,6]

我的解法

内部创建一个vector用以存储结果，然后用swap函数交换。

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        vector<int> temp;
        int i = 0;
        int j = 0;
        
        while(i < m && j < n)
        {
            if(nums1[i] < nums2[j]) temp.push_back(nums1[i++]);
            
            else temp.push_back(nums2[j++]);
        }
        
        for(i; i < m; i++)
        {
            temp.push_back(nums1[i]);
        }
        
        for(j; j < n; j++)
        {
            temp.push_back(nums2[j]);
        }
        
        nums1.swap(temp);
    }
};

其它解法1：直接赋值，不用push_back

要知道，出题给出的条件中，nums1后面为啥补0，还不是为了赋值方便嘛…

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        int i = m - 1;  // nums1的最后一个
        int j = n - 1;  // nums2的最后一个
        int k = m + n - 1;  // 混合数组的最后一个

        while(i >= 0 && j >=0)
        {
            if(nums1[i] > nums2[j]) nums1[k--] = nums1[i--];
            else nums1[k--] = nums2[j--];
        }

        while(j >= 0)
        {
            nums1[k--] = nums2[j--];
        }
    }
};

其它解法2：对解法1的简化

把其它解法1的两个while合在一起。

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        int i = m - 1;  // nums1的最后一个
        int j = n - 1;  // nums2的最后一个
        int k = m + n - 1;  // 混合数组的最后一个

        while(j >=0)
        {
            if( i >= 0 && nums1[i] > nums2[j]) nums1[k--] = nums1[i--];
            else nums1[k--] = nums2[j--];
        }
    }
};

其它解法3-5：用到vector自带的api

虽然这几个解法不太符合出题的考察点，但是也看看吧，主要学习灵活运用自带的api

解法3：新建存的数据为nums1从开始到m的数据，再insert nums2，然后swap新建的vector和nums1，最后用sort排序。

class Solution {
public:
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n)
{
    vector<int> temp(nums1.begin(), nums1.begin() + m);
    temp.insert(temp.end(), nums2.begin(), nums2.end());
    nums1.swap(temp);
    sort(nums1.begin(), nums1.end());
}

解法4：先把nums1后面的0去掉，再把对把nums2 insert到nums1后面，最后用sort排序。

class Solution {
public:
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n)
{
    nums1.resize(m);
    nums1.insert(nums1.end(), nums2.begin(), nums2.end());
    sort(nums1.begin(), nums1.end());

解法5：用copy直接把nums1的m后面的数据换成nums2的数据，再执行sort。

class Solution {
public:
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n)
{
    copy(nums2.begin(),nums2.end(),nums1.begin() + m);
    sort(nums1.begin(), nums1.end());