Leetcode 88 题解

这道题其实比较简单，通过依次比较大小并且按顺序大小放入到一个数组中即可，但是由于最终要放到原数组中，这里比较麻烦。一种比较简单的做法是另外开辟一块空间，然后在合并之后再复制一遍，如下所示。

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

空间复杂度O(m+n)，时间复杂度O(n)。提交之后，看了别人的解法，发现从后边开始时不需要额外开辟数组，如下所示。

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        int i1 = m-1, i2 = n-1, cur = m+n-1;
        while(i1 >= 0 && i2 >= 0){
            if(nums1[i1] >= nums2[i2])
                nums1[cur--] = nums1[i1--];
            else
                nums1[cur--] = nums2[i2--];                    
        }
        while(i1 >= 0) nums1[cur--] = nums1[i1--];
        while(i2 >= 0) nums1[cur--] = nums2[i2--];   
    }
};

这种思维的确十分精巧，而且这种思想在操作系统内存管理中有用到。