Loading [MathJax]/jax/output/CommonHTML/config.js
首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >专栏 >leetcode刷题(32)——88. 合并两个有序数组

leetcode刷题(32)——88. 合并两个有序数组

作者头像
老马的编程之旅
发布于 2022-06-22 05:31:20
发布于 2022-06-22 05:31:20
19300
代码可运行
举报
文章被收录于专栏:深入理解Android深入理解Android
运行总次数:0
代码可运行

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

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

示例:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
输入:
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6],       n = 3

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

方法1: 投机取巧,感觉面试并不会喜欢这种解法,直接两个合并为一个数组,然后用Api进行排序,但此方法没有利用到两个数组都是分别已经排序好的特点。

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        for(int i=0;i<n;i++){
            nums1[m+i]=nums2[i];
        }
        Arrays.sort(nums1);
    }
}

方法2:双指针 / 从前往后 一般而言,对于有序数组可以通过 双指针法 达到O(n + m)O(n+m)的时间复杂度。

最直接的算法实现是将指针p1 置为 nums1的开头, p2为 nums2的开头,在每一步将最小值放入输出数组中。

由于 nums1 是用于输出的数组,需要将nums1中的前m个元素放在其他地方,也就需要 O(m)O(m) 的空间复杂度。

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
class Solution {
  public void merge(int[] nums1, int m, int[] nums2, int n) {
    // Make a copy of nums1.
    int [] nums1_copy = new int[m];
    System.arraycopy(nums1, 0, nums1_copy, 0, m);

    // Two get pointers for nums1_copy and nums2.
    int p1 = 0;
    int p2 = 0;

    // Set pointer for nums1
    int p = 0;

    // Compare elements from nums1_copy and nums2
    // and add the smallest one into nums1.
    while ((p1 < m) && (p2 < n))
      nums1[p++] = (nums1_copy[p1] < nums2[p2]) ? nums1_copy[p1++] : nums2[p2++];

    // if there are still elements to add
    if (p1 < m)
      System.arraycopy(nums1_copy, p1, nums1, p1 + p2, m + n - p1 - p2);
    if (p2 < n)
      System.arraycopy(nums2, p2, nums1, p1 + p2, m + n - p1 - p2);
  }
}

复杂度分析 时间复杂度 : O(n + m)。 空间复杂度 : O(m)。

方法3 : 双指针 / 从后往前 标签:从后向前数组遍历 1.因为 nums1 的空间都集中在后面,所以从后向前处理排序的数据会更好,节省空间,一边遍历一边将值填充进去 2.设置指针 len1 和 len2 分别指向 nums1 和 nums2 的有数字尾部,从尾部值开始比较遍历,同时设置指针 len 指向 nums1 的最末尾,每次遍历比较值大小之后,则进行填充 3.当 len1<0 时遍历结束,此时 nums2 中还有数据未拷贝完全,将其直接拷贝到 nums1 的前面,最后得到结果数组 时间复杂度:O(m+n)

巧妙之处在于while ((p1 >= 0) && (p2 >= 0))采用了&符号,当跳出循环时候必然是nums1已经遍历完毕,此时直接拷贝nums2剩余的数,如果p2还大于0的话

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
class Solution {
  public void merge(int[] nums1, int m, int[] nums2, int n) {
    // two get pointers for nums1 and nums2
    int p1 = m - 1;
    int p2 = n - 1;
    // set pointer for nums1
    int p = m + n - 1;

    // while there are still elements to compare
    while ((p1 >= 0) & (p2 >= 0))
      // compare two elements from nums1 and nums2 
      // and add the largest one in nums1 
      nums1[p--] = (nums1[p1] < nums2[p2]) ? nums2[p2--] : nums1[p1--];

    // add missing elements from nums2
    System.arraycopy(nums2, 0, nums1, 0, p2 + 1);
  }
}
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2019-11-19,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
暂无评论
推荐阅读
编辑精选文章
换一批
画解算法:88. 合并两个有序数组
https://leetcode-cn.com/problems/merge-sorted-array/
灵魂画师牧码
2019/07/11
4430
画解算法:88. 合并两个有序数组
88 合并两个有序数组
给你两个有序整数数组 nums1 和 nums2,请你将 nums2 合并到 nums1 中,使 nums1 成为一个有序数组。
木瓜煲鸡脚
2021/01/18
9850
88 合并两个有序数组
LeetCode-88. 合并两个有序数组(java)
进阶:你可以设计实现一个时间复杂度为 ​​O(m + n)​​ 的算法解决此问题吗?
bug菌
2023/05/27
4170
LeetCode-88. 合并两个有序数组(java)
leetcode 88. 合并两个有序数组 js实现
给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2,另有两个整数 m 和 n ,分别表示 nums1 和 nums2 中的元素数目。
蓓蕾心晴
2022/11/28
1.1K0
LeetCode | 合并两个有序数组
题目 88. 合并两个有序数组 - 力扣(LeetCode) 给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2,另有两个整数 m 和 n ,分别表示 nums1 和 nums2 中的元素数目。 请你 合并 nums2 到 nums1 中,使合并后的数组同样按 非递减顺序 排列。 注意:最终,合并后数组不应由函数返回,而是存储在数组 nums1 中。为了应对这种情况,nums1 的初始长度为 m + n,其中前 m 个元素表示应合并的元素,后 n 个元素为 0 ,应忽略。nums2 的长度为 n 。 示例 1:
yiyun
2023/03/27
8910
LeetCode | 合并两个有序数组
LeetCode 图解 | 88. 合并两个有序数组
题目来源于 LeetCode 上第 88 号问题:合并两个有序数组。题目难度为 Easy。
五分钟学算法
2020/05/19
7910
LeetCode 图解 | 88.  合并两个有序数组
LeetCode刷题(4)【移除元素&合并两个有序数组】(C语言)(含图解)
27. 移除元素 - 力扣(LeetCode) (leetcode-cn.com)
半生瓜的blog
2023/05/12
3870
LeetCode刷题(4)【移除元素&合并两个有序数组】(C语言)(含图解)
LeetCode每日一题:合并两个有序数组
链接: 合并两个有序数组 ---- 这题有个要求:能不能使用O(m+n)的时间复杂度完成? 那当然是有的! 思路:用两个指针分别指向两个数组的尾部!这个很关键! 然后从后向前遍历。又题目可知,nums1的大小肯定是m+n的,且nums1的后半部分是空的,直接覆盖是没影响的。 所以就是将nums2中的元素与nums1中的比较,谁大就先放谁进去。 class Solution { public: void merge(vector<int>& nums1, int m, vector
利刃大大
2023/04/12
1540
LeetCode每日一题:合并两个有序数组
(Leetcode 2021 刷题计划) 88. 合并两个有序数组
给你两个有序整数数组 nums1 和 nums2,请你将 nums2 合并到 nums1 中,使 nums1 成为一个有序数组。
windism
2021/04/05
2850
leetcode-easy-array-合并两个有序数组
给你两个有序整数数组 nums1 和 nums2,请你将 nums2 合并到 nums1 中,使 nums1 成为一个有序数组。
shengjk1
2020/09/01
2780
88. 合并两个有序数组
给你两个按 「非递减顺序」 排列的整数数组 nums1 和 nums2,另有两个整数 m 和 n ,分别表示 nums1 和 nums2 中的元素数目。
chuckQu
2022/08/19
6230
合并两个有序数组
给你两个有序整数数组 nums1 和 nums2,请你将 nums2 合并到 nums1 中,使 nums1 成为一个有序数组。
_kyle
2020/11/13
9970
88. 合并两个有序数组
给定两个有序整数数组 nums1 和 nums2,将 nums2 合并到 nums1 中,使得 num1 成为一个有序数组。
张伦聪zhangluncong
2022/10/26
6560
LeetCode 4. 寻找两个有序数组的中位数(二分查找,难)
来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/median-of-two-sorted-arrays 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
Michael阿明
2020/07/13
1.1K0
LeetCode 4. 寻找两个有序数组的中位数(二分查找,难)
Leetcode No.88 合并两个有序数组
给你两个有序整数数组 nums1 和 nums2,请你将 nums2 合并到 nums1 中,使 nums1 成为一个有序数组。
week
2021/05/06
2110
合并两个有序数组
有两个排序的整数数组,分别是数组1和数组2,将数组2合并到数组1中,合并以后的数组1,仍是有序数组。 提示:
一觉睡到小时候
2019/07/03
1.3K0
六十六、Leetcode数组系列(中篇)
作者介绍:Runsen目前大三下学期,专业化学工程与工艺,大学沉迷日语,Python, Java和一系列数据分析软件。导致翘课严重,专业排名中下。.在大学60%的时间,都在CSDN。决定今天比昨天要更加努力。前面文章,点击下面链接
润森
2020/06/16
5810
算法题 合并两个有序数组
 我们为两个数组分别设置一个指针 p1与 p2来作为队列的头部指针,p1作为nums1的指针,p2作为nums1的指针,从两数组坐标0,开始比大小,谁小谁的数组坐标下的数,用cur记录后,放入sorted数组,这个数组的指针++,如次以此比较,直到两个数组比较完成。
人不走空
2024/02/20
1560
【LeetCode12】合并两个有序数组
我发现最近做的题目都可以用双指针算法来解决,这道题也一样,我们定义两个指针p1和p2,分别从数组1指定位置(由m决定)和数组2的尾端开始往前遍历。
Sam Gor
2019/07/08
7000
【LeetCode12】合并两个有序数组
力扣 (LeetCode)-合并两个有序数组,字典,散列表
Github来源:力扣 (LeetCode)|刷题打卡 | 求星星 ✨ | 给个❤️关注,❤️点赞,❤️鼓励一下作者
达达前端
2021/03/22
1.5K0
力扣 (LeetCode)-合并两个有序数组,字典,散列表
相关推荐
画解算法:88. 合并两个有序数组
更多 >
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档
本文部分代码块支持一键运行,欢迎体验
本文部分代码块支持一键运行,欢迎体验