Leetcode088

LeetCode088：合并两个有序数组         给你两个有序整数数组 nums1 和 nums2，请你将 nums2 合并到 nums1 中，使 nums1 成为一个有序数组。 ```cpp 说明: 初始化 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]

#### 解法一：基于sort排序方法

&#160; &#160; &#160; &#160;<font color="black" size="4">首先将nums2中的元素按照顺序插入到nums1的m-1到m+n-1的位置，
然后用sort排序对nums1进行非降序排序</font>

```cpp
class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        int i = m - 1;
        int j = n - 1;

        for (int k = m + n - 1; k>m - 1;)
        {
            nums1[k--] = nums2[j--];
        }
        sort(nums1.begin(), nums1.end());
    }
};

解法二：基于最大遍历的方法

       首先我们定义两个指针初始值为i = m - 1; j = n - 1;
然后将较大值填充到nums1的最后面。
最后如果nums2中还有剩余，就依次填充到nums1最前面就行了。

class Solution2 {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        int i = m - 1;
        int j = n - 1;
        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--];

    }
};

解法三：基于for范围排序方法(提倡，用时最少，0ms)

       首先我们利用基于for范围的循环将nums2中的元素放到nums1后面，
然后对nums1进行sort排序即可。

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

解法四：基于copy的方法(提倡，用时最少，0ms)

       copy 是将数组中的一段改成另一段，被改变的数组长度不变
然后对nums1进行sort排序即可。

class Solution4 {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        //copy 是将数组中的一段改成另一段，被改变的数组长度不变
        copy(nums2.begin(), nums2.end(), nums1.begin() + m);
        sort(nums1.begin(), nums1.end());
    }
};

main()函数

#include "stdafx.h"
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
    vector<int> nums1,nums2;
    int Size1, Size2;
    cout << "请输入nums1的数组大小 Size1: " << endl;
    cin >> Size1;
    int Currval1;
    for (int i = 0; i < Size1; i++)
    {
        cin >> Currval1;
        nums1.push_back(Currval1);
    }

    cout << "请输入nums2的数组大小 Size2: " << endl;
    cin >> Size2;
    int Currval2;
    for (int i = 0; i < Size2; i++)
    {
        cin >> Currval2;
        nums2.push_back(Currval2);
    }

    Solution2 answer;
    answer.merge(nums1, Size1, nums2, Size2);
    vector<int>::iterator it;
    for (it=nums1.begin();it!=nums1.end();it++)
    {
        cout << *it << " ";
    }

    system("pause");
    return 0;
}