LeetCode88 合并两个有序数组

LeetCode 合并两个有序数组

• 题目
• 解题
• • 解题一：双指针
  • 解题二：逆向双指针

题目

解题

解题一：双指针

利用数组 nums1 与 nums2 已经被排序的性质，使用双指针方法：将两个数组看作队列，每次从两个数组头部取出比较小的数字放到结果中。

// javascript
var merge = function(nums1, m, nums2, n) {
    let p1 = 0, p2 = 0, next;
    const sorted = new Array(m + n).fill(0);
    while (p1 < m || p2 < n) {
        if (p1 === m) next = nums2[p2++];
        else if (p2 === n) next = nums1[p1++];
        else if (nums1[p1] < nums2[p2]) next = nums1[p1++];
        else next = nums2[p2++];
        sorted[p1 + p2 - 1] = next;
    }
    for (let i = 0; i < m + n; i++) {
        nums1[i] = sorted[i];
    }
};
           

解题二：逆向双指针

// javascript
var merge = function(nums1, m, nums2, n) {
    let p1 = m - 1, p2 = n - 1, prev;
    let tail = m + n - 1;
    while (p1 >= 0 || p2 >= 0) {
        if (p1 === -1) prev = nums2[p2--];
        else if (p2 === -1) prev = nums1[p1--];
        else if (nums1[p1] > nums2[p2]) prev = nums1[p1--];
        else prev = nums2[p2--];
        nums1[tail--] = prev;
    }
};