88. Merge Sorted Array

https://leetcode.com/problems/merge-sorted-array/description/

Given two sorted integer arrays A and B, merge B into A as one sorted array.

Thoughts

两个排好序的数组nums1和nums2，将nums2和nums1按所有元素从小到大排序放到nums1里，nums1有足够剩余空间。nums1后面是空的，按从大到小从后面一个个插入。再来检查下当要被覆盖的元素移到m内时的正确性。这个程序只要被覆盖的index >= nums1当前最大值的index，则肯定不会出现错误。当要被覆盖的是m-1位置时，指向nums1最大元素的指针最多在m-1；当被覆盖的是m-2位置时，指向nums1最大值的index肯定不能是m-1了，因为现在已经有n + 1个按照从大到小排好序了，只剩下m+n-(n+1) = m-1个元素未排序，只能最多指向nums2[m-2]了。依此类推，程序正确。

Code

/*
 * @lc app=leetcode id=88 lang=cpp
 *
 * [88] Merge Sorted Array
 */

// @lc code=start
class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        for (int it = m + n - 1, i = m - 1, j = n - 1; it >= 0; --it) {
            const auto a = i >= 0 ? nums1[i] : INT_MIN, b = j >= 0 ? nums2[j] : INT_MIN;
            if (a < b) {
                nums1[it] = nums2[j--];
            } else {
                nums1[it] = nums1[i--];
            }
        }
        
    }
};
// @lc code=end

Analysis

TC: O(n), SC: O(1)