首页 > 其他分享 >力扣由浅至深 每日一题.16 ​ 合并两个有序数组​

力扣由浅至深 每日一题.16 ​ 合并两个有序数组​

时间:2024-03-27 23:34:05浏览次数:29  
标签:16 int 复杂度 力扣 ++ 数组 一题 nums1 nums2

日复一日的生活里也会有新的快乐

                                  —— 24.3.27

合并两个有序数组

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

请你 合并 nums2 到 nums1 中,使合并后的数组同样按 非递减顺序 排列。(next[data]>=data)

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

方法一:直接合并后排序

最直观的方法是先将数组 nums2放进数组 nums1的尾部,然后直接对整个数组进行排序。

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);
    }
}

复杂度分析

时间复杂度:O((m+n)log⁡(m+n))。
排序序列长度为 m+n,套用快速排序的时间复杂度即可,平均情况为 O((m+n)log⁡(m+n))。

空间复杂度:O(log⁡(m+n))
排序序列长度为 m+n,套用快速排序的空间复杂度即可,平均情况为 O(log⁡(m+n))

方法二:双指针方法

方法一没有利用数组 nums1与 nums2已经被排序的性质。为了利用这一性质,我们可以使用双指针方法。这一方法将两个数组看作队列,每次从两个数组头部取出比较小的数字放到结果中。

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int p1 = 0, p2 = 0;
        int[] sorted = new int[m + n];
        int cur;
        while (p1 < m || p2 < n) {   
# 如果数组1达到最大长度,则合并后总的数组3的新元素等于数组2p2++位置的元素
            if (p1 == m) {     
                cur = nums2[p2++];
            } else if (p2 == n) {    
# 如果数组2达到最大长度,则合并后总的数组3的新元素等于数组1p1++位置的元素
                cur = nums1[p1++];
            } else if (nums1[p1] < nums2[p2]) {
# 如果数组1,2都未达到最大长度,则合并后总的数组3的新元素等于数组1的p1位置元素和数组2p2位置元素的较小值
                cur = nums1[p1++];
            } else {
                cur = nums2[p2++];
            }
# 最终新数组长度发生改变
            sorted[p1 + p2 - 1] = cur;
        }
# 将合并后的新数组赋值到数组1中,不用返回,但是存在数组1的地址中
        for (int i = 0; i < m + n; ++i) {
            nums1[i] = sorted[i];
        }
    }
}

复杂度分析

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

空间复杂度:O(m+n)。
需要建立长度为 m+nm+nm+n 的中间数组 sorted。

方法三:逆向双指针

双指针数组元素从后向前比较,我们在把大的值放入nums1中时,如果放的是nums1,则nums1空出一个位置 放的是nums2时,才会占位置,而空出的位置刚好是够nums2用的 

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int a = m - 1, b = n - 1, c = m + n - 1;
        while (a >= 0 && b >= 0) {
            nums1[c--] =(nums1[a] > nums2[b] ? nums1[a--] : nums2[b--]);
        }

        while (a >= 0) {
            nums1[c--] = nums1[a--];
        }

        while (b >= 0) {
            nums1[c--] = nums2[b--];
        }
    }
}

复杂度分析

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

空间复杂度:O(1)。
直接对数组 nums1 原地修改,不需要额外空间。

标签:16,int,复杂度,力扣,++,数组,一题,nums1,nums2
From: https://blog.csdn.net/m0_73983707/article/details/137051830

相关文章

  • 力扣:回文数判断 java
    给你一个整数 x ,如果 x 是一个回文整数,返回 true ;否则,返回 false 。回文数是指正序(从左向右)和倒序(从右向左)读都是一样的整数。例如,121 是回文,而 123 不是。示例1:输入:x=121输出:true示例2:输入:x=-121输出:false解释:从左向右读,为-121。从右向左读,......
  • 力扣:移除元素 java
    给你一个数组 nums 和一个值 val,你需要 原地 移除所有数值等于 val 的元素,并返回移除后数组的新长度。不要使用额外的数组空间,你必须仅使用 O(1) 额外空间并 原地 修改输入数组。元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。说明:为什么返回......
  • 「CF1677D」Tokitsukaze and Permutations的题解
    「CF1677D」TokitsukazeandPermutations首先,若\(v\)的后\(k\)个数中有一个\(>0\),或有\(v_i>i-1(i\in[1,n])\),则无解。我们发现,每次对\(p\)进行了一次操作后,\(v\)也一定会对应的进行一次变化,所以统计\(p\)的个数就相当于统计\(v\)的个数。我们对于每一次冒泡排序......
  • CF EDU163 F-组合数、范德蒙德卷积
    “总感觉这题是诈骗题…”link:https://codeforces.com/contest/1948/problem/F[!题意]有\(n\)个袋子,每个袋子有\(a_i\)个金币,\(b_i\)个银币,金币的价格固定是\(1\),每个银币的价格服从\(B(1,\frac{1}{2})\)的分布。\(q\)次询问,每次问一段区间\([l,r]\)内背包总的......
  • 面试题 16.01. 交换数字
    题目链接:本题要求不能借助临时变量交换\(a\)和\(b\)的值,应想到借助异或运算的性质。本题亦是异或运算的一个经典应用。a=a^b;//记a^b的值为cb=b^a=b^(a^b)=a^(b^b)=a^0=a;a=a^b=(a^b)^a=b^(a^a)=b;即实现了两个数的交......
  • 【力扣】36. 有效的数独 - 力扣(LeetCode)
    这里主要是记录一些我做这个题遇到的问题及解决办法目录1.问题描述1.1思路分析:2.程序代码及注释:1.问题描述1.1思路分析:  对于个题目而言,我只使用了一个参数,其中我的主要思路就是暴力循环求解,总体思路就是先判断每行是否符合要求,在判断每列是否符合要求、然后......
  • 16使用正则表达式处理字符串
    1<!DOCTYPEhtml>2<htmllang="en">3<head>4<metacharset="UTF-8">5<metaname="viewport"content="width=device-width,initial-scale=1.0">6<title>Document......
  • P1605 迷宫 (对坐标dfs)
    写在前面:        我可太牛了!第一次写就能得70分!信心倍增!        OMG!五分钟找出漏洞,我真是太棒啦!        这道题要注意,一定要将初始起点坐标状态设为true!题目:代码:#include<algorithm>#include<iostream>#include<cstring>#include<queue>#in......
  • 文心一言 VS 讯飞星火 VS chatgpt (223)-- 算法导论16.3 5题
    五、证明:如果我们将字母表中字符按频率单调递减排序,那么存在一个最优编码,其码字长度是单调递增的。文心一言:为了证明这个结论,我们可以使用霍夫曼编码(HuffmanCoding)作为示例,它是一种广泛使用的最优前缀编码方法。霍夫曼编码满足题目中的要求:如果我们将字母表中字符按频率......
  • buuctf之pwn1_sctf_2016
    一、查看属性首先还是必要的查看属性环节:可以知道该文件是一个x86架构下的32位小段ELF程序我们可以先执行一下看看:二、静态分析扔到IDA中看一下,主函数没什么用,这里的vuln函数是必进的,我们进去看看vuln函数这个函数整体分析下来,我也看不太明白是干啥,看到了fgets函数,但......