LeetCode题练习与总结:合并两个有序数组--88

2024-05-08 01:36

本文主要是介绍LeetCode题练习与总结:合并两个有序数组--88,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

一、题目描述

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

请你 合并 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
  • -10^9 <= nums1[i], nums2[j] <= 10^9

二、解题思路

1. 初始化指针

  • p1:指向 nums1 的有效元素末尾,初始值为 m - 1
  • p2:指向 nums2 的末尾,初始值为 n - 1
  • p:指向 nums1 的末尾,即合并后数组的末尾,初始值为 m + n - 1

2. 比较并合并

  • 当 p1 >= 0 且 p2 >= 0 时,比较 nums1[p1] 和 nums2[p2]
  • 将较大的元素复制到 nums1[p] 的位置,并将相应的指针向前移动一位(即 p--p1-- 或 p2--)。

3. 处理剩余元素

  • 如果 nums1 的所有元素已经合并完成(即 p1 < 0),而 nums2 还有剩余元素,直接将 nums2 的剩余元素复制到 nums1 的前端。
  • 由于 nums1 的前 m 个元素已经是排好序的,且 nums1 的长度是 m + n,所以不需要单独处理 nums1 剩余的元素。

4. 结束条件

  • 当 p2 < 0 时,表示 nums2 的所有元素已经合并完成,此时合并过程结束。

通过以上步骤,可以在不使用额外空间的情况下,将 nums2 合并到 nums1 中,并且保证合并后的数组仍然有序。

三、具体代码

class Solution {public void merge(int[] nums1, int m, int[] nums2, int n) {int p1 = m - 1; // nums1的有效元素末尾int p2 = n - 1; // nums2的末尾int p = m + n - 1; // nums1的末尾// 从后往前遍历,比较并填充nums1while (p1 >= 0 && p2 >= 0) {nums1[p--] = (nums1[p1] > nums2[p2]) ? nums1[p1--] : nums2[p2--];}// 如果nums2还有剩余元素,直接复制到nums1的前端while (p2 >= 0) {nums1[p--] = nums2[p2--];}}
}

四、时间复杂度和空间复杂度

1. 时间复杂度
  • 该算法的主要时间消耗在于遍历两个数组中的元素,并进行比较和复制操作。
  • while 循环会执行 m + n 次,因为每次循环都会将一个元素放到最终位置,直到所有元素都被放置完毕。
  • 因此,时间复杂度为 O(m + n)。
2. 空间复杂度
  • 该算法没有使用额外的数组空间,只是使用了几个额外的变量来存储指针位置。
  • 变量 p1p2 和 p 占用的空间是常数级别的,与输入数组的大小无关。
  • 因此,空间复杂度为 O(1),即常数空间复杂度。

综上所述,该算法的时间复杂度为 O(m + n),空间复杂度为 O(1)。

五、总结知识点

1. 数组的操作

  • 通过索引访问数组元素:nums1[p1] 和 nums2[p2]
  • 通过索引修改数组元素:nums1[p] = nums1[p1] 或 nums1[p] = nums2[p2]

2. 指针的概念

  • 使用指针(即索引变量)来跟踪数组中的位置。在这里,p1p2 和 p 都是指针,它们表示当前正在比较或复制的元素的位置。

3. 循环结构

  • 使用 while 循环来重复执行比较和复制操作,直到所有元素都被处理。

4. 条件语句

  • 使用条件语句(if-else 的三元操作符形式)来决定哪个元素应该被复制到 nums1 的当前位置。

5. 自减运算符

  • 使用自减运算符 -- 来将指针向前移动,即从数组的末尾向开始位置移动。

6. 数组合并的逻辑

  • 从两个数组的末尾开始比较,将较大的元素逐个移动到 nums1 的末尾,这样可以避免使用额外的空间,并且能够保持元素的顺序。

7. 数组的长度和索引

  • 数组的长度是从 0 开始的,所以数组的最后一个元素的索引是 length - 1

8. 边界条件的处理

  • 当 p1 或 p2 小于 0 时,表示一个数组已经处理完毕,只需要将另一个数组的剩余元素复制到 nums1 中。

以上就是解决这个问题的详细步骤,希望能够为各位提供启发和帮助。

这篇关于LeetCode题练习与总结:合并两个有序数组--88的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/968947

相关文章

HarmonyOS学习(七)——UI(五)常用布局总结

自适应布局 1.1、线性布局(LinearLayout) 通过线性容器Row和Column实现线性布局。Column容器内的子组件按照垂直方向排列,Row组件中的子组件按照水平方向排列。 属性说明space通过space参数设置主轴上子组件的间距,达到各子组件在排列上的等间距效果alignItems设置子组件在交叉轴上的对齐方式,且在各类尺寸屏幕上表现一致,其中交叉轴为垂直时,取值为Vert

哈希leetcode-1

目录 1前言 2.例题  2.1两数之和 2.2判断是否互为字符重排 2.3存在重复元素1 2.4存在重复元素2 2.5字母异位词分组 1前言 哈希表主要是适合于快速查找某个元素(O(1)) 当我们要频繁的查找某个元素,第一哈希表O(1),第二,二分O(log n) 一般可以分为语言自带的容器哈希和用数组模拟的简易哈希。 最简单的比如数组模拟字符存储,只要开26个c

学习hash总结

2014/1/29/   最近刚开始学hash,名字很陌生,但是hash的思想却很熟悉,以前早就做过此类的题,但是不知道这就是hash思想而已,说白了hash就是一个映射,往往灵活利用数组的下标来实现算法,hash的作用:1、判重;2、统计次数;

hdu2241(二分+合并数组)

题意:判断是否存在a+b+c = x,a,b,c分别属于集合A,B,C 如果用暴力会超时,所以这里用到了数组合并,将b,c数组合并成d,d数组存的是b,c数组元素的和,然后对d数组进行二分就可以了 代码如下(附注释): #include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<que

hdu 1166 敌兵布阵(树状数组 or 线段树)

题意是求一个线段的和,在线段上可以进行加减的修改。 树状数组的模板题。 代码: #include <stdio.h>#include <string.h>const int maxn = 50000 + 1;int c[maxn];int n;int lowbit(int x){return x & -x;}void add(int x, int num){while

day-51 合并零之间的节点

思路 直接遍历链表即可,遇到val=0跳过,val非零则加在一起,最后返回即可 解题过程 返回链表可以有头结点,方便插入,返回head.next Code /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}*

git使用的说明总结

Git使用说明 下载安装(下载地址) macOS: Git - Downloading macOS Windows: Git - Downloading Windows Linux/Unix: Git (git-scm.com) 创建新仓库 本地创建新仓库:创建新文件夹,进入文件夹目录,执行指令 git init ,用以创建新的git 克隆仓库 执行指令用以创建一个本地仓库的

二分最大匹配总结

HDU 2444  黑白染色 ,二分图判定 const int maxn = 208 ;vector<int> g[maxn] ;int n ;bool vis[maxn] ;int match[maxn] ;;int color[maxn] ;int setcolor(int u , int c){color[u] = c ;for(vector<int>::iter

整数Hash散列总结

方法:    step1  :线性探测  step2 散列   当 h(k)位置已经存储有元素的时候,依次探查(h(k)+i) mod S, i=1,2,3…,直到找到空的存储单元为止。其中,S为 数组长度。 HDU 1496   a*x1^2+b*x2^2+c*x3^2+d*x4^2=0 。 x在 [-100,100] 解的个数  const int MaxN = 3000

状态dp总结

zoj 3631  N 个数中选若干数和(只能选一次)<=M 的最大值 const int Max_N = 38 ;int a[1<<16] , b[1<<16] , x[Max_N] , e[Max_N] ;void GetNum(int g[] , int n , int s[] , int &m){ int i , j , t ;m = 0 ;for(i = 0 ;