合并两个有序数组


题目

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

要求时间复杂度为 O(n)

说明:

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

示例:

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

输出:[1,2,2,3,5,6]

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/merge-sorted-array
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

分析

这道题是根据之前 有序数组的平方 的 tag: 双指针 找来的。

所以我第一时间就想着如何通过 双指针 来做这道题。

因为本身是两个有序数组,且 num1 有足够的容量来容纳 nums2 的元素,所以我想到用两个指针来分别标记 nums1nums2 的最后一个元素, idx 来标记新元素需要放到到 nums1 的位置,初始为 nums1 的最有一个元素位置

然后依次比较, 谁大, 谁就放到 nums1idx 下标位置

直到 m 和 n 都小于 0,即 num1nums2 中元素都找到合适的位置为止。

代码

private static int[] merge(int[] nums1, int m, int[] nums2, int n) {
    int left = m - 1;
    int right = n - 1;
    int idx = m + n - 1;
    do {
        if (left >= 0 && right >= 0) {
            int num1 = nums1[left];
            int num2 = nums2[right];
            if (num1 >= num2) {
                nums1[idx--] = num1[left--];
                left--;
            } else {
                nums1[idx--] = num2;
                right--;
            }
        } else if (right >= 0) {
                nums1[idx--] = nums2[right];
                right--;
        }

    } while (right >= 0);
    return nums1;
}

这份代码是我第一次写的代码,虽然有写的匆忙的缘故, 整体看起来十分繁琐。

但胜在代码的整体思路,表达的很清晰。也很符合我当时的解题思路。

  1. 找到双指针的位置,以及待插入元素的位置
  2. 根据双指针找到两个元素,根据比较结果,插入对应的位置,同时挪动双指针
  3. 当某一方指针移动完毕后, 就只移动另一方指针,防止数组下标越界

然后我看了下 leetcode 上其他人的解法,思路基本都一致,只是别人的代码却十分简洁。

归根结底, 我想, 还是我的思路不是特别清晰, 对于各种临界值的判断,还不是特别准且。

理解完大佬们的代码后,我又写了一份代码:

private static int[] merge3(int[] nums1, int m, int[] nums2, int n) {
    // 这里在拿 idx 的同时, 对 m、n 做了处理,让他们处于正确的位置上
    int idx = m-- + n-- - 1;

    // 这个 while 只处理 m、n 都大于 0 的情况
    while (m >= 0 && n >= 0) {
        // 使用谁,就让谁的指针移动
        nums1[idx--] = nums1[m] > nums2[n] ? nums1[m--] : nums2[n--];
    }

    // 这里只判断 n 的情况
    // 因为 m 即使没有走完,剩下的元素也都已经处于正确位置,就不用再处理
    while (n >= 0) {
        nums1[idx--] = nums2[n--];
    }
    return nums1;
}

这段代码看起来, 就比之前的代码要简洁的太多,相关说明亦以放到注释里,不再赘述。


文章作者: peifeng
版权声明: 本博客所有文章除特別声明外,均采用 CC BY-NC-ND 4.0 许可协议。转载请注明来源 peifeng !
 上一篇
删除排序数组中的重复元素 删除排序数组中的重复元素
题目 给定一个排序数组,你需要在 原地 删除重复出现的元素,使得每个元素只出现一次,返回移除后数组的新长度。 不要使用额外的数组空间,你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。 示例 1: 给定数组 nums
2020-10-18
下一篇 
有序数组的平方 有序数组的平方
题目 给定一个按非递减顺序排序的整数数组 A,返回每个数字的平方组成的新数组,要求也按非递减顺序排序。 示例 1: 输入:[-4,-1,0,3,10]输出:[0,1,9,16,100]示例 2: 输入:[-7,-3,2,3,11]输出:[4
2020-10-16
  目录