LeetCode 每日一题 88. 合并两个有序数组

88. 合并两个有序数组

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

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

题目描述：把归并结果存到第一个数组上。

需要从尾开始遍历，否则在 nums1 上归并得到的值会覆盖还未进行归并比较的值。

代码:

语法糖版本:

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        nums1.erase(nums1.begin() + m, nums1.end());
        copy(nums2.begin(), nums2.end(), back_inserter(nums1));
        sort(nums1.begin(), nums1.end());
    }
};

双指针版:

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