栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

LeetCode(88题)--合并两个有序数组[JAVA]

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

LeetCode(88题)--合并两个有序数组[JAVA]

文章目录
  • 一、题目描述与分析
  • 二、解题代码与算法描述

一、题目描述与分析

 由题可知要合并nums1和nums2,并且nums1的长度为n+m。题目理解比较容易,直接看算法。

二、解题代码与算法描述 解决方法1

我们可以直接将nums1数组的0全部复制成nums2数组的元素值。然后再去进行排序。这也是我第一时间想到的算法。

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        for(int i=0;i 

提交结果:

虽然可以通过,但这用到了java中的快速排序方法,时间复杂度较高。有什么更好的算法呢,仔细读题可发现,每个数组都是非递减排序。这也有了下面的算法。

解决方法2

我们可以用2个指针来分别对应数组,新建立一个空的数组,从小到大比较。nums1[nums1index]小于等于nums2[nums2index],就把小的值放到新数组,然后把nums1的索引值向后移一位再进行比较。反之也是一样。最后把新数组的值遍历都赋值给num1数组。这样就实现了。并且时间复杂度为O(n+m).

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        

        //O(m+n)
        int k=m+n;
        int[] temp=new int[k];
        for(int index=0,nums1index=0,nums2index=0;index=m说明nums1数组值取完,直接取nums2数组值
            if(nums1index>=m){
                temp[index]=nums2[nums2index++];
            }else if(nums2index>=n){//nums2index>=n说明nums2数组值取完,直接取nums1数组值
                temp[index]=nums1[nums1index++];
            }else if(nums1[nums1index]<= nums2[nums2index]){//数组1值小于数组二,所以把数组1该值赋值
                temp[index]=nums1[nums1index++];
            }else{//数组2值小于数组1,所以把数组2该值赋值
                temp[index]=nums2[nums2index++];
            }
        }
        //把数组赋值给数组1
        for(int i=0;i 

提交结果:

也是超越了100%的用户。

这是从小到大取每一个数放到新的数组里,当然也可以不用新建数组。因为nums1数组已经有n长度的值为0的空间,所以可以从大到小赋值,指针先指向每个有效数组的最后一个有效元素(nums1index=m-1,nums2index=n-1)去比较大小,nums2[nums2index]>=nums1[nums1index]这就说明nums2[nums2index]值大,要放到后面,所以(nums1[m+n-1]=nums2[nums2index]),然后总指针-1,nums2index-1。反之也是一样。直到总指针减到0就完成了。这个是反向思路,其实就是正向思路的逆过程,大家可以去试试。


转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/961647.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号