专栏首页Java那些事每天一道leetcode88-合并两个有序数组

每天一道leetcode88-合并两个有序数组

题目

每天一道leetcode88-合并两个有序数组 分类:链表 中文链接: https://leetcode-cn.com/problems/merge-sorted-array/ 英文链接 https://leetcode.com/problems/merge-sorted-array/

题目详述

给定两个有序整数数组 nums1 和 nums2,将 nums2 合并到 nums1 中,使得 num1 成为一个有序数组。 说明: 初始化 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]

题目详解

使用额外空间的思路

  • 混合插入有序数组,由于两个数组都是有序的,所有只要按顺序比较大小即可。最先想到的方法是建立一个m+n大小的新数组,然后逐个从A和B数组中取出元素比较,把较小的加入新数组,然后在考虑A数组有剩余和B数组有剩余的两种情况,最后在把新数组的元素重新赋值到A数组中即可。

代码

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int [] result = new int[m+n];
        int i =0,j=0,k=0;
        while(i < m && j < n)
        {
            if(nums1[i] < nums2[j]){
                result[k++] = nums1[i++];
            }else{
                result[k++] = nums2[j++];
            }
        }
        if(i != m)
        {
            while(i < m)
            {
                result[k++] = nums1[i++];
            }
        }
        if(j != n)
        {
            while(j < n)
            {
                result[k++] = nums2[j++];
            }
        }
        k = 0;
        for(i=0;i<nums1.length;i++)
            nums1[i] = result[k++];

    }
}

代码讲解

  • 5-12行,比较num1数组与nums2数组,哪个小,就存入result中
  • 13-26行 就是两个数组,可能有一个没遍历完,那么把这个没遍历完的继续添加到result数组后面
  • 28-29行 就是把result数组复制到nums1中。

不使用额外空间的思路

  • 由于合并后A数组的大小必定是m+n,所以从最后面开始往前赋值,先比较A和B中最后一个元素的大小,把较大的那个插入到m+n-1的位置上,再依次向前推。如果A中所有的元素都比B小,那么前m个还是A原来的内容,没有改变。如果A中的数组比B大的,当A循环完了,B中还有元素没加入A,直接用个循环把B中所有的元素覆盖到A剩下的位置。

代码

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int k = m + n - 1;
        int i = m-1;int j = n-1;
        while(i >=0 && j >= 0)
        {
            if(nums1[i] > nums2[j])
            {
                nums1[k--] = nums1[i--];
            }else{
                nums1[k--] = nums2[j--];
            }
        }
        if(i > 0)
        {
            while(i >= 0)
            {
                nums1[k--] = nums1[i--];
            }
        }
        if(j >= 0)
        {
            while(j >= 0)
            {
                nums1[k--] = nums2[j--];
            }
        }
    }
}

代码讲解

  • 5-13行就是从数组nums1和数组nums2的后面开始遍历,谁大就把谁存到nums1的后面(这里注意看示例,nums1的后面是一堆0,代表空闲的空间,m和nums1的数组长度是不一样的~
  • 14-20行 就是如果nums1前面有数字没遍历完,那么就把nums1的数字继续保留到nums1中,其实这6行代码可以不要,因为nums1的数字就是有序的,不需要再次复制了,nums1的前面的数字已经存在于nums1中了;
  • 21-27行 就是如果nums2前面还有数字没遍历完,那么就把nums2中数字复制到nums1中,这里是必须要要用到,因为nums2中数字可不在nums1中。

本文分享自微信公众号 - 程序员乔戈里(CXYqiaogeli),作者:乔戈里qgl

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

原始发表时间:2018-11-16

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 15 道二叉树手写算法题(二)

    在上一期讲到,树和链表的手写算法题在面试中出现的频率最高。也正是因为这样,如果你马上就要参加面试,但之前没有刷多少算法题,那么很建议你先看看树和链表相关的题目。...

    乔戈里
  • 【漫画】腾讯面试,我竟然输给了final关键字

    任何变量前被 final 修饰就是 final 变量,定义的类前被 final 修饰就是 final 类,任何方法前被 final 修饰就是final方法。

    乔戈里
  • 每天一道剑指offer-二叉树的镜像

    今天的题目 每天的题目见github(看最新的日期): https://github.com/gzc426 具体的题目可以去牛客网对应专题去找。

    乔戈里
  • 【专知-关关的刷题日记16】Leetcode 88. Merge Sorted Array

    题目 Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as on...

    WZEARW
  • 【每日算法Day 96】腾讯面试题:合并两个有序数组

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

    godweiyang
  • Q88 Merge Sorted Array

    Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one s...

    echobingo
  • LeetCode 88. 合并两个有序数组

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

    村雨遥
  • LeetCode刷题DAY 22:合并两个有序数组

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

    三猫
  • [Leetcode][python]Merge Sorted Array/合并两个有序数组

    将两个有序数组合并成为一个。 注意点: 第一个数组有充足的空间来存放第二个数组中的元素 第一个数组的有效长度为m,第二个的有效长度为n 在原数组...

    后端技术漫谈
  • Leetcode#88. Merge Sorted Array(合并两个有序数组)

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

    武培轩

扫码关注云+社区

领取腾讯云代金券