Mind palace

some thoughts

0%

88. Merge Sorted Array

Posted on Edited on In Disqus:
Symbols count in article: 1.1k Reading time ≈ 1 mins.

O(m+n) time O(1) space
关键是从后往前扫描！！

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        for (int i = m + n - 1, i1 = m - 1, i2 = n - 1; i2 >= 0; --i) {
            if (i1 >= 0) {
                nums1[i] = nums1[i1] > nums2[i2] ? nums1[i1--] : nums2[i2--];
            } else {
                nums1[i] = nums2[i2--];
            }
        }
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        for (int i = m + n - 1, i1 = m - 1, i2 = n - 1; i >= 0; --i) {
            if (i1 >= 0 && i2 >= 0) {
                nums1[i] = nums1[i1] > nums2[i2] ? nums1[i1--] : nums2[i2--];
            } else if (i2 >= 0) { // i1到头了，只扫nums2即可
                nums1[i] = nums2[i2--];
            } else { // i2到头了，nums1保持不变，不用再扫了
                break;
            }
        }
    }
};

O(m+n) time O(m+n) space

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        vector<int> res(m + n);
        for (int i = 0, j = 0; i < m || j < n;) {
            int a = i < m ? nums1[i] : INT_MAX;
            int b = j < n ? nums2[j] : INT_MAX;
            res[i + j] = min(a, b);
            if (res[i + j] == a) ++i;
            else ++j;
        }
        nums1 = res;
    }
};