专栏首页IT那个小笔记88 合并两个有序数组

88 合并两个有序数组

题目信息

题目地址:https://leetcode-cn.com/problems/merge-sorted-array/

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

说明:

初始化 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]

提示:

-10^9 <= nums1[i], nums2[i] <= 10^9
nums1.length == m + n
nums2.length == n

解法一:双指针(顺序)

很直接的就是双指针扫描,与上次我们在链表时写过合并有序链表同样的通过扫描与大小比较最终扫描完两个序列(m+n),前者是新建一个头节点然后遍历过程中慢慢连。这边也是可以创建一个数组,每扫描一个往里面设置值。

看下题目可知实际的元素数量是m,n完整数组是可能有多余空间,并且num1的空闲可以容纳nums2的有效元素,就是说我们直接把nums1作为结果数组,新建的数组装num1的实际元素

有了思路之后理一下具体的过程:

代码如下:

public void merge(int[] nums1, int m, int[] nums2, int n) {
    // 1.得到num1实际元素的数组
    int [] nums1_copy = new int[m];
    /*
    for(int i = 0; i < m; i++){
        nums1_copy[i] = nums[i];
    }
    */
    System.arraycopy(nums1, 0, nums1_copy, 0, m);
    
    // 扫描两个素材数组的指针
    int p = 0;
    int q = 0;
    // 结果数组(num1)待设值位置的指针
    int cur = 0;

    // 2.挨个比较设值
    while ((p < m) && (q < n)){
        nums1[cur++] = (nums1_copy[p] < nums2[q]) ? nums1_copy[p++] : nums2[q++];
    }

    // 3.加入最后多余的一段
    if (p < m)
      System.arraycopy(nums1_copy, p, nums1, p + q, m + n - p - q);
    if (q < n)
      System.arraycopy(nums2, q, nums1, p + q, m + n - p - q);
}

时间上的话看三组操作m+min(m,n)+(m-n)或(n-m)因此为m+n,遍历了两组元素嘛O(m+n) 空间就是nums1_copy也就是O(m)

解法二:双指针(逆序)

解这题一开始我就在想是不是原地就可以(不用创建数组),但如果在解法一的过程中把num2的值设过去,那边就必须得存被替换的值。并且可能一直是num2小也是说那边还是需要一个中间数组。

也就是为了那一块的值创建了m大小的数组,为什么我们能拿num1为结果数组?不就是它有空闲的一块地方么,那么我们何必不用呢!反而另开一块呢!直接用后面的地方不就不存在替换了吗!

因此我们就用后面这块,直接倒序设值,整理过程如下:

情况一:最终前面小的一块在num1

情况一:最终前面小的一块在num2

代码如下:

public void merge(int[] nums1, int m, int[] nums2, int n) {
    // 定义两个指针并指向元素末端
    int p = m - 1;
    int q = n - 1;
    // 注意初始化当前指针在整个元素m+n的末端并不是整个num1的末端
    int cur = m + n - 1;

    // 1.挨个比较设值
    while (p >= 0 && q >= 0){
        nums1[cur--] = (nums1[p] < nums2[q]) ? nums2[q--] : nums1[p--];
    } 
    // 2.可能nums2前面有余
    System.arraycopy(nums2, 0, nums1, 0, q + 1);
}

时间复杂度仍然是不可避免的O(m+n) 空间复杂度O(1)

总结

这题还是比较简单的,主要是考虑到添加缓存与当前空间的问题。很多时候我们的中间变量或者中间数组是否真的该加。场上是否有不用的空间不用的变量,这是我们需要考虑的!剔除冗余无效代码

本文分享自微信公众号 - IT那个小笔记(Jasper-zh_blog),作者:木瓜煲鸡脚

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-12-27

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 88合并两个有序数组

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

    宇宙之一粟
  • LeetCode 88. 合并两个有序数组

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

    村雨遥
  • LeetCode 88. 合并两个有序数组

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

    freesan44
  • Leetcode No.88 合并两个有序数组

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

    week
  • LeetCode 图解 | 88. 合并两个有序数组

    题目来源于 LeetCode 上第 88 号问题:合并两个有序数组。题目难度为 Easy。

    五分钟学算法
  • 【leetcode系列】88.合并两个有序数组

    这道题目其实和基本排序算法中的 merge sort非常像,但是 merge sort 很多时候,合并的时候我们通常是 新建一个数组,这样就很简单。但是这道题目...

    lucifer210
  • 画解算法:88. 合并两个有序数组

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

    灵魂画师牧码
  • 【LeetCode】88. 合并两个有序数组 双指针

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

    韩旭051
  • ​LeetCode刷题实战88:合并两个有序数组

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

    程序IT圈
  • Leetcode|sort+双指针|88. 合并两个有序数组

    SL_World
  • (Leetcode 2021 刷题计划) 88. 合并两个有序数组

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

    windism
  • Day11【LeetCode每日一题】88. 合并两个有序数组

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

    公众号guangcity
  • Leetcode#88. Merge Sorted Array(合并两个有序数组)

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

    武培轩
  • 合并两个有序数组(leetcode.88)

    euclid
  • 合并两个有序数组

    有两个排序的整数数组,分别是数组1和数组2,将数组2合并到数组1中,合并以后的数组1,仍是有序数组。 提示:

    一觉睡到小时候
  • 合并两个有序数组

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

    _kyle
  • [算法] - 合并两个有序数组

    夹胡碰
  • 【LeetCode12】合并两个有序数组

    我发现最近做的题目都可以用双指针算法来解决,这道题也一样,我们定义两个指针p1和p2,分别从数组1指定位置(由m决定)和数组2的尾端开始往前遍历。

    Sam Gor
  • 20T44-合并两个有序数组

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

    木又AI帮

扫码关注云+社区

领取腾讯云代金券