88. Merge Sorted Array 合并两个数组

Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.

Note:
You may assume that nums1 has enough space (size that is greater or equal to m + n) to hold additional elements from nums2. The number of elements initialized in nums1 and nums2 are m and n respectively.

题目的意思：nums1的大小已经比m+n要大，只不过认为只有前m个有意义。

方法1：使用stl，首先将第二个数组复制到第一个数组的位置，然后使用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.begin()+m+n);
    }
};

方法2：不适用stl，从两个数组的末尾位置开始往前比较，这样可以省去移动的时间。

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        int mn=m+n-1;//末尾标号
        int i=m-1,j=n-1;
        if(n==0) return;
        if(m!=0){
        while(mn>=0)
        {
            if(i<0||j<0) break;
            if(nums1[i]>nums2[j]) nums1[mn--]=nums1[i--];
            else  nums1[mn--]=nums2[j--];
        }
        }
        if(i<0)
        {
            while(mn>=0) nums1[mn--]=nums2[j--];
        }
        else while(mn>=0) nums1[mn--]=nums1[i--];

    }
};

方法2：改进版本.while的判断条件变化，能够包含两个数组为空的情况。同时，当j先变为0时，不需要对剩下的数值做改变

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        int k=m+n-1;//末尾标号
        int i=m-1,j=n-1;
        while(i>=0&&j>=0)//注意这里的判断条件的改变
        {
            if(nums1[i]>nums2[j]) nums1[k--]=nums1[i--];
            else nums1[k--]=nums2[j--];
        }
        while(j>=0)//如果是j先达到0，不需要做其他操作，因为是复制到nums1
        nums1[k--]=nums2[j--];


    }
};