88. Merge Sorted Array

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

Note:

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

Example:

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

Output: [1,2,2,3,5,6]

---

把两个已排序数组合并成一个有序数组。注意是保存到nums1中。我一开始理解的是在合并过程中不能借助额外空间，所以用两个指针i,j指向两个数组，然后每次从nums2中找第一个小于nums1[i]的数，然后交换nums1[i]和nums2[j]，再调整nums2使有序。如此下去，nums1就是合并有序数组中的较小数组部分。
这个版本的完整代码如下：

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

本代码提交AC，用时6MS。但是只击败了15%的人，仔细看看算法实现，最坏复杂度是$O(n*m)$，因为如果nums1={6,7,8,9,10}，nums2={1,2,3,4,5}，则nums1[i]每和nums2[0]交换一次，nums2调整时都要交换n-1次，所以最坏复杂度是$O(n*m)$。所以应该还有更好的算法。
看题解，发现我没有很好利用nums1的数组大小至少是n+m这个信息，这说明合并之后的整个数组，最大下标只能是n+m-1，所以我们可以对nums1和nums2从后往前比较，把更大的元素依次在nums1[n+m-1]往前放，这样共3个指针，他们之间不会有overlap。此算法的复杂度只有$O(max(n,m))$。

完整代码如下：

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n)
    {
        if (n == 0)
            return;
        int i = m – 1, j = n – 1, k = m + n – 1;
        while (i >= 0 || j >= 0) {
            int a = i >= 0 ? nums1[i] : INT_MIN;
            int b = j >= 0 ? nums2[j] : INT_MIN;
            if (a > b) {
                nums1[k–] = a;
                i–;
            }
            else {
                nums1[k–] = b;
                j–;
            }
        }
    }
};

本代码提交AC，用时3MS，果然快多了。