LeetCode - 合并两个有序数组(No.88)

#88review

• issue #88 - reference

• idea - reference

#88 details

给你两个有序整数数组 nums1 和 nums2，请你将 nums2 合并到 nums1 中，使 nums1 成为一个有序数组。

初始化 nums1 和 nums2 的元素数量分别为 m 和 n 。你可以假设 nums1 有足够的空间（空间大小等于 m + n）来保存 nums2 中的元素。

• e.g.1

输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
输出：[1,2,2,3,5,6]

• e.g.2

输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
输出：[1,2,2,3,5,6]

idea

algorithm gif can be checked in idea - reference

我们从nums1的后方开始，设置目前的移动指针cur、遍历nums1有效区间的指针i以及遍历nums2有效区间的指针j。

首先我们将i和j初始化，即

int i = --m;
int j = --n;

初始化cur为合并后num1的末尾位置，即

int cur = m + n - 1;

接着通过双指针i和j分别遍历nums1和nums2，会遇到一下几种情况，

• 当i指向的nums1元素大于j指向的nums2元素，此时将i指向的元素与cur指向的元素交换，并且各自前进一个，即

swap(nums1[i]， nums1[cur]);
i--;
cur--

? 简化可得，

swap(nums1[cur--], nums1[i--]);

• 当i指向的nums1元素小于等于j指向的nums2元素，此时将j指向的元素与cur指向的元素交换，并且各自前进一个，简化过程同上，即

swap(nums1[cur--], nums2[j--]);

遍历过程代码如下，

while (n >= 0) {
    while (m >= 0 && nums1[i] > nums2[j]) {
        swap(nums1[cur--], nums1[i--]);
    }
    swap(nums1[cur--], nums2[j--]);
}

完整代码

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

LeetCode - 合并两个有序数组(No.88)

原文：https://www.cnblogs.com/litun/p/leetcode_solution__88.html