精华内容
下载资源
问答
  • 合并两个有序数组 千次阅读 多人点赞
    2020-11-22 00:03:16

    今天的题目是 合并两个有序数组,我们先来看下题目要求:

    给你两个有序整数数组 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]
    
    

    看到这个题目第一眼,你是不是也和我一样想到了直接把两个数组放在同一个数组里边,然后调用Arrays.sort() 然后就直接得到了结果呢,这样是可以的 但是浪费了题目中的 原数组也是有序的这个条件,且这样做的复杂度很高,为什么呢?

    nums2数组拷贝到nums1数组,因为数组在物理内存中是连续的存储单元,合并数组时,
    本身并不会耗费很多的时间和空间,但是sort方法的底层是一种快速排序的方法,时间复杂度是O(nlog n)
    
    

    因为两个数组本身就是有序的了,我们可以利用这个条件,在原数组遍历一遍的时候直接排序就好了,所以 双指针,他来了!

    public void merge(int[] nums1, int m, int[] nums2, int n) {
            int k = m + n - 1 ; //两个数组合在一起 最后那个数的下标
            int i = m - 1 ; // nums1 的最后一个数的下标
            int j = n - 1 ;// nums2 的最后一个数的下标
            while(i>=0 && j>=0) {  //从后往前遍历 直到最前边的数字都遍历完
                if(nums1[i] < nums2[j]){    //当nums1的最后一个数字小于nums2的最后一个数字
                nums1[k--] = nums2[j--] ;//这说明nums2最后一个数字是合并之后数组中值最大的后头的位置
                }else{  //否则放在远处不动 继续向下遍历
                    nums1[k--] = nums1[i--] ;
                }
            }
            while(j>=0) nums1[k--]= nums2[j--] ;  //当nums1已经排序完之后 但是nums2还有数据
        }
    

    写完之后,我们来测试一下;

    在这里插入图片描述
    搞定!
    2020年11月22日00:02:47

    更多相关内容
  • 主要介绍了Python实现的合并两个有序数组算法,涉及Python针对数组的遍历、计算、追加等相关操作技巧,需要的朋友可以参考下
  • 本文实例讲述了PHP实现合并两个有序数组的方法。分享给大家供大家参考,具体如下: $arr1 = array(1,2,3,4,5,6,7,8); $arr2 = array(3,4,5,7,9,10); //方法1 function mergeOrderly1($arr1,$arr2){ $i=0;$j=0; $...
  • 主要介绍了Python3合并两个有序数组代码实例,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下
  • 主要为大家详细介绍了C++实现两个有序数组合并,文中示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
  • js代码-(算法)合并两个有序数组
  • js代码-2.2 双指针法 合并两个有序数组
  • 合并两个有序数组1.题目: (合并两个有序数组)2. 示例3.解答步骤4. 提交结果(提交用时和内存消耗) 声明: 题目均来自力扣,网址力扣官网, 如有侵权,告知必删! 本题地址: 点击我跳转本题地址 1.题目: ...

    声明: 题目均来自力扣,网址力扣官网, 如有侵权,告知必删!
    本题地址: 点击我跳转本题地址

    1.题目: (合并两个有序数组)

    给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2,另有两个整数 m 和 n ,分别表示 nums1 和 nums2 中的元素数目。
    请你 合并 nums2 到 nums1 中,使合并后的数组同样按 非递减顺序 排列。
    注意:最终,合并后数组不应由函数返回,而是存储在数组 nums1 中。为了应对这种情况,nums1 的初始长度为 m + n,其中前 m 个元素表示应合并的元素,后 n 个元素为 0 ,应忽略。nums2 的长度为 n 。

    2. 示例

    在这里插入图片描述

    3.解答步骤

    思路都在注释上! 请大家自主阅读程序!

    ⭐ 本篇注意点: 本题主要思想

    答: 因为要将两个⭐有序数组,归并且保持有序。则需要对比两个数组的元素值,较小的一个放到临时数组,并且移动下标,依次对比,完成归并有序数组。

    class Solution {
        public void merge(int[] nums1, int m, int[] nums2, int n) {
            // 创建一个用于存放合并排序后的数组
            int[] tempArray = new int[m + n];
            // 创建一个用于遍历i,j的下标
            int i,j;
            i=j=0;
            // 创建一个temp数组的下标
            int tempIndex=0;
    
            // 进行一个while循环
            // 依次从两个数组的初始位置开始比较
            // 将较小的一方放到临时数组
            while(i<m && j<n) {
                if(nums1[i] < nums2[j]) {
                    tempArray[tempIndex++] = nums1[i++];
                } else {
                    tempArray[tempIndex++] = nums2[j++];
                }
            }
    
            // 假如有一个数组遍历完
            // 而另一个数组并不空时
            // 应当将这个数组的值全部放进tempArray
            for( ; i<m;) {
                tempArray[tempIndex++] = nums1[i++];
            }
            for(; j<n; ) {
                tempArray[tempIndex++] = nums2[j++];
            }
    
            // 将合并归并好的数组赋值给nums1
            for(int k=0; k<m+n; k++) {
                nums1[k] = tempArray[k];
            }
        }
    }
    

    4. 提交结果(提交用时和内存消耗)

    在这里插入图片描述

    展开全文
  • leetCode第88题 合并两个有序数组 给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2,另有两个整数 m 和 n ,分别表示 nums1 和 nums2 中的元素数目。 请你 合并 nums2 到 nums1 中,使合并后的数组同样按 非...

    问题描述

    leetCode第88题 合并两个有序数组
    给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2,另有两个整数 m 和 n ,分别表示 nums1 和 nums2 中的元素数目。
    请你 合并 nums2 到 nums1 中,使合并后的数组同样按 非递减顺序 排列。
    注意:最终,合并后数组不应由函数返回,而是存储在数组 nums1 中。为了应对这种情况,nums1 的初始长度为 m + n,其中前 m 个元素表示应合并的元素,后 n 个元素为 0 ,应忽略。nums2 的长度为 n 。

    示例1:

    输入:nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
    输出:[1,2,2,3,5,6]
    解释:需要合并 [1,2,3] 和 [2,5,6] 。
    合并结果是 [1,2,2,3,5,6] ,其中斜体加粗标注的为 nums1 中的元素。
    

    示例2:

    输入:nums1 = [1], m = 1, nums2 = [], n = 0
    输出:[1]
    解释:需要合并 [1] 和 [] 。
    合并结果是 [1] 。
    

    示例3:

    输入:nums1 = [0], m = 0, nums2 = [1], n = 1
    输出:[1]
    解释:需要合并的数组是 [] 和 [1] 。
    合并结果是 [1] 。
    注意,因为 m = 0 ,所以 nums1 中没有元素。nums1 中仅存的 0 仅仅是为了确保合并结果可以顺利存放到 nums1 中。
    

    提示:

    nums1.length == m + n
    nums2.length == n
    0 <= m, n <= 200
    1 <= m + n <= 200
    -109 <= nums1[i], nums2[j] <= 109
    

    进阶:

    你可以设计实现一个时间复杂度为 O(m + n) 的算法解决此问题吗?
    

    碰到的问题

    问题并不复杂,nums1的总长度为m+n,前m个是nums的元素,后n个元素是0,只要将后n个元素改为nums2的元素,再对nums1进行排序即可。
    但我想对我碰到的问题进行一个分享
    在这里插入图片描述

    ## 错误代码 第一版
    class Solution:
        def merge(self, nums1: [int], m: int, nums2: [int], n: int) -> None:
            """
            Do not return anything, modify nums1 in-place instead.
            """
            nums1 = nums1[:m]
            nums1 = nums1+nums2
            nums1.sort()
            print(nums1)
    

    在这里插入图片描述
    python的print()函数输出列表时会自带一个空格,起初我还认为不是WA,而是presentation error
    于是对输出格式进行了更改

    ## 错误代码 第二版
    class Solution:
        def merge(self, nums1: [int], m: int, nums2: [int], n: int) -> None:
            """
            Do not return anything, modify nums1 in-place instead.
            """
            nums1 = nums1[:m]+nums2
            nums1.sort()
            print("[",end="")
            print(",".join(str(x) for x in nums1),end='')
            print("]",end='')
    

    更改后空格确实没了,但还是错误
    在这里插入图片描述
    在这里插入图片描述
    这时我才注意到输出是[1,2,3,0,0,0],可是我将nums1进行输出得到的是正确结果。
    我最初以为是nums1.sort()出现了问题,于是改成nums1 = sorted(nums1),并进行测试

    class Solution:
        def merge(self, nums1: [int], m: int, nums2: [int], n: int) -> None:
            """
            Do not return anything, modify nums1 in-place instead.
            """
            print(id(nums1))
            nums1 = nums1[:m]+nums2
            print(id(nums1))
            nums1 = sorted(nums1)
            print(id(nums1))
    
    '''
    运行结果
    2550904029568
    2550904029312
    2550904029248
    '''
    

    查看变量的地址,发现在python中,每次对列表进行 nums1 = ‘’’ 的赋值操作,nums1的地址都会被改变。用sorted(nums1)和nums1.sort()却不会改变nums1的地址。
    将nums1 = nums1[:m]+nums2这种写法在本题中是错误的。而应该对m后的元素直接进行变更,而不是将列表合并赋值给nums1。

    ## 正确代码
    class Solution:
        def merge(self, nums1: [int], m: int, nums2: [int], n: int) -> None:
            """
            Do not return anything, modify nums1 in-place instead.
            """
            for i in range(n):
                nums1[m+i] = nums2[i]
            nums1.sort()
    

    算法优化

    这种写法确实简单,但效率并不高。题目中说到两个列表是有序的,而将两个列表合并后成为无序表,之后再进行排序这种做法并没有利用好有序表这个条件,所以可以进行优化。
    在n1和n2上分别设立一个指针,比较两个数值的大小,将较小的元素存放到一个临时列表,然后移动指针,继续比较。最后把临时列表的值一个一个赋值到n1。
    这种方法只把n1和n2遍历了一遍,时间复杂度为O(m+n)

    # python3
    class Solution:
        def merge(self, nums1: [int], m: int, nums2: [int], n: int) -> None:
            """
            Do not return anything, modify nums1 in-place instead.
            """
            k = m+n
            temp = [0]*k  #临时列表
            n1Index = 0  #定义两个指针
            n2Index = 0
            for i in range(k):
                if n1Index >= m:   #  nums1的元素已经取完,直接把nums2的元素填入
                    temp[i] = nums2[n2Index]
                    n2Index += 1
                elif n2Index >= n:   #nums2的元素已经取完,直接把nums1的元素填入
                    temp[i] = nums1[n1Index]
                    n1Index += 1
                elif nums1[n1Index] < nums2[n2Index]:
                    temp[i] = nums1[n1Index]
                    n1Index += 1
                else:
                    temp[i] = nums2[n2Index]
                    n2Index += 1
            nums1[:] = temp
    

    在上述做法中,引入了临时列表temp,但在nums1中有几个0元素占用了空间,没有被利用起来。
    这意味着可以进行优化,不需要引入临时列表temp。
    在两个有序表中,6比3大,那么意味着6应该放在最后一个,之后指针2前移,5比3大,5应该在倒数第二个,2比3小,倒数第三个应该是3,2与2一样大,倒数第四个应该是2.。这样就不必引入临时列表了。
    >在这里插入图片描述

    class Solution2:
        def merge(self, nums1: [int], m: int, nums2: [int], n: int) -> None:
            """
            Do not return anything, modify nums1 in-place instead.
            """
            k = m + n
            n1Index = m-1
            n2Index = n-1
            for i in range(k-1,-1,-1):
                if n1Index < 0:  #n1已经取完,剩下的空直接填n2
                    nums1[i] = nums2[n2Index]
                    n2Index -= 1
                elif n2Index < 0: # n2已经取完,n1就不需要变动了
                    break
                elif nums1[n1Index] > nums2[n2Index]:
                    nums1[i] = nums1[n1Index]
                    n1Index -= 1
                else:
                    nums1[i] = nums2[n2Index]
                    n2Index -= 1
    
    展开全文
  • leetcode算法88.合并两个有序数组

    热门讨论 2022-02-17 11:46:18
    ❤️❤️❤️感谢各位朋友接下来的阅读❤️❤️❤️ 文章目录 一、leetcode算法 1、合并两个有序数组 1.1、题目 1.2、思路 1.3、答案 一、leetcode算法 1、合并两个有序数组 1.1、题目 给你两个按 非递减顺序 排列...

    👏👏👏

    哈喽!大家好,我是【学无止境小奇】,一位热爱分享各种技术的博主!😍😍😍

    ⭐【学无止境小奇】的创作宗旨:每一条命令都亲自执行过,每一行代码都实际运行过,每一种方法都真实实践过,每一篇文章都良心制作过。✊✊✊

    ⭐【学无止境小奇】的博客中所有涉及命令、代码的地方,除了提供图片供大家参考,另外会在图片下方提供一份纯文本格式的命令或者代码方便大家粘贴复制直接执行命令或者运行代码。🤝🤝🤝

    ⭐如果你对技术有着浓厚的兴趣,欢迎关注【学无止境小奇】,欢迎大家和我一起交流。😘😘😘

    ❤️❤️❤️感谢各位朋友接下来的阅读❤️❤️❤️

    一、leetcode算法

    1、合并两个有序数组

    1.1、题目

    给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2,另有两个整数 m 和 n ,分别表示 nums1 和 nums2 中的元素数目。

    请你 合并 nums2 到 nums1 中,使合并后的数组同样按 非递减顺序 排列。

    注意:最终,合并后数组不应由函数返回,而是存储在数组 nums1 中。为了应对这种情况,nums1 的初始长度为 m + n,其中前 m 个元素表示应合并的元素,后 n 个元素为 0 ,应忽略。nums2 的长度为 n 。

    示例 1:
    输入:nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
    输出:[1,2,2,3,5,6]
    解释:需要合并 [1,2,3] 和 [2,5,6] 。
    合并结果是 [1,2,2,3,5,6] ,其中斜体加粗标注的为 nums1 中的元素。
    示例 2:

    输入:nums1 = [1], m = 1, nums2 = [], n = 0
    输出:[1]
    解释:需要合并 [1] 和 [] 。
    合并结果是 [1] 。
    示例 3:

    输入:nums1 = [0], m = 0, nums2 = [1], n = 1
    输出:[1]
    解释:需要合并的数组是 [] 和 [1] 。
    合并结果是 [1] 。
    注意,因为 m = 0 ,所以 nums1 中没有元素。nums1 中仅存的 0 仅仅是为了确保合并结果可以顺利存放到 nums1 中。

    1.2、思路

    思路一:此题我们可以使用逆向三指针来解决问题,因为nums1的长度是m+n所以可以将所有的数据放入到nums1中,这个时候我们先定义三个指针,第一个指针为p1,指向nums1数组中有数据的最后一个下标,也就是m-1;第二个指针为p2,指向nums2数组中有数据的最后一个下标,就是是n-1;第三个指针为nums1中最后一个位置的下标,也就是m+n-1。
    这里大致思路就是从后面开始查找首先将两个数组中最大的一个数找出来,并放入nums1数组中的最后一个位置,然后由大到小的查找。

    1.3、答案

    在这里插入图片描述

    class Solution {
        public void merge(int[] nums1, int m, int[] nums2, int n) {
            //定义两个数组中有数的最后一位下标
            int p1 = m - 1, p2 = n -1;
            //定义第一个数组中最后一位下标
            int tail = m + n - 1;
            //定义数值变量
            int end;
    
            while (p1 >= 0 || p2 >= 0){
                //如果m初始值为0,那么这里p1就会是-1,所以要加以判断。
                if(p1 == -1){
                    end = nums2[p2];
                    p2--;
                    //如果n初始值为0,那么这里p2就会是-1,所以要加以判断。
                }else if(p2 == -1){
                    end = nums1[p1];
                    p1--;
                    //nums1最后一位数大于nums2最后一位数,那么就将nums最后一位数赋值给变量,这一位数肯定是最大值
                }else if(nums1[p1] > nums2[p2]){
                    end = nums1[p1];
                    p1--;
                } else{
                    end = nums2[p2];
                    p2--;
                }
                //我们将最大值从nums1数组最后一位进行赋值
                nums1[tail] = end;
                tail--;
            }
        }
    }
    

    复杂度分析

    时间复杂度:O(m+n)。
    指针移动单调递减,最多移动 m+n 次,因此时间复杂度为 O(m+n)。

    空间复杂度:O(1)。

    展开全文
  • 88. 合并两个有序数组 1、直接合并后排序 将nms2放到nums1的后面,然后进行排序 var merge = function(nums1, m, nums2, n) { // 将splice将nums2的值放到nums1的后面 // 从m位置开始删除nums1.length-m的元素,...
  • 合并两个有序数组 88. 合并两个有序数组 - 力扣(LeetCode) (leetcode-cn.com) 思路和合并两个有序链表相同 //两个数组元素分别比较,把数组中小的放到新数组,再把新数组拷回去 void merge(int* nums1, int nums1...
  • js-合并两个有序数组

    2022-05-06 21:58:48
    js-合并两个有序数组
  • 给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2,另有两个整数 m 和 n ,分别表示 nums1 和 nums2 中的元素数目。 请你 合并 nums2 到 nums1 中,使合并后的数组同样按 非递减顺序 排列。 输入:nums1 = ...
  • 示例1: 输入:l1 = [1,2,4], l2 = [1,3,4] 输出:[1,1,2,3,4,4] 示例2: 输入:l1 = [], l2 = [] 输出:[] 思路:先建立一数组l3,然后... len(l2): # 当某一个数组遍历到最后一位, 另外一个数组还没遍历完 .
  • 合并两个升序排序的整型数组为一个新的升序整型数组并输出。 输入格式: 首先输入第一个数组的数据个数后输入第一个数组按升序排序的数据,然后再输入第二个数组的数据个数,最后输入第二个数据按升序排序的数据。...
  • PTA 一维数组 7-4 合并两个有序数组

    千次阅读 2021-12-02 22:11:03
    已知两组递增的有序数列(数据无重复)。编写程序将两组数列合并为一组递增的有序数列,且合并后的该组数列中相同的整数只出现一次。 如(1​ 5 ​7 ​9​)∪( 2​ 3​ 7 ​10​)⇒(1​ 2​ 3 ​5​ 7 ​9 ​10​)
  • 合并两个有序数组为新的有序数组 描述: 合并两个升序排序的整型数组为一个新的升序整型数组并输出。 输入格式: 首先输入第一个数组的数据个数后输入第一个数组按升序排序的数据,然后再输入第二个数组的数据个数,...
  • 给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2,另有两个整数 m 和 n ,分别表示 nums1 和 nums2 中的元素数目。 请你 合并 nums2 到 nums1 中,使合并后的数组同样按 非递减顺序 排列。 注意:最终,合并...
  • 给你两个按非递减顺序排列的整数数组nums1和nums2,另有两个整数m和n,分别表示nums1和nums2中的元素数目。
  • 题目描述 当时想的很简单 就把num2 复制到 num1 的后面,再对 num1 排序 ...再来看第二种方法,这种就是先使用 num1 后面空的位置,比较两个数组的元素大小,再放进 num1 的空位,这样得到的新的num1 是有序
  • 对于两个数组[45,56,78,82]和[32,48,72,79,83,85,92]进行合并,使合并数组有序的。即[32,45,48,56,72,78,82,83,85,92] 方法1:类似插入排序 // An highlighted block import java.util.Arrays; class Oneday { ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 89,780
精华内容 35,912
关键字:

合并两个有序数组