顺序表经典的OJ题

news/2024/5/20 7:13:17 标签: 算法, 数据结构, 顺序表, OJ题

题目一 移除元素:

题目要求:

  • 给你一个数组 nums 和一个值 val。
  • 你需要 原地 除所有数值等于 val 的素,并返回移除后数组的新长度.不要使用额外的数组空间。
  • 你必须仅使用 0(1) 额外空间并 原地 修改输入数组元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

图例:

注意,本题要求:不要使用额外的数组空间。

如上图中情况,我们使用双指针解法 

图例: 

起始:

 

开始遍历数组,src指向的数据为val,所以进行src++

 

 src指向的数据不是val,把src指向的数据交给dst所在的位置

随后src和dst都++

 

如此遍历下去,直到src越界或者遍历结束最后返回dst

代码输入:

nums是数组名 numsSize是数组大小 val是需要删除的数据,最后返回dst 

 

题目二 合并两个有序数组:

题目内容:

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

注意:最终,合并后数组不应由函数返回,而是存储在数组 nums1 中。

为了应对这种情况,nums1 的初始长度为 m + n,其中前 m 个元素表示应合并的元素,后n 个元素为 0 ,应忽略。 nums2 的长度为 n 。 

举例:

  • 做法:定义三个指针,第一个和第二个分别在数组1数组2的最后一位有效数据的位置数,而第三个指针放在第一个数组的末端位置
  • 随后开始指针1和指针2的向前循环遍历比较,在二者指向的数据中,数据大的往指针三所指向的位置进行存放
  • 存放完毕后,被存放的那个数据所代表的指针往前移,没有被存放的数据继续进行比较
  • 同时指针3朝前移动
  • 能怎么做的原因:两个按非递减(递增)顺序排列的整数数组 nums1 和 nums2 

图例:

初始:

 

相互比较 6 更大进行指针3的插入

 

同时指针3往前移,6所代表的指针1也往前移 

 

并且指针2所指的数据再次和指针1所指的数据继续比较

指针1和指针3再度往前移动,再度比较和移动后

 

指针1越界了,因为指针一越界,且因为两个数组本质起始是从小到大进行排列,所以指针3指向的位置接下来就应该存放指针2指向的数据,然后二者走完遍历结束 

 

代码输入:

  • l1=m-1 , l2=n-1 二者分别指向最后一位有效数据(有效数据相当于数组大小)
  • m+n是空间大小,但在这里是数组1的大小 

同时这里只有2种情况,那就是数组2走完了,数组1没走完,但是呢数组1和数组2的数据全部是放在数组1中的,数组2走完也是表明数组2的数据是比数组1内的数据都大所以放在数组1的后排,而数组1走完表明数组1比数组2的数据都大,所以数组2的数据需要放在在数组1的前排 


http://www.niftyadmin.cn/n/5086253.html

相关文章

06-Zookeeper选举Leader源码剖析

上一篇:05-Zookeeper典型使用场景实战 一、为什么要看源码 提升技术功底:学习源码里的优秀设计思想,比如一些疑难问题的解决思路,还有一些优秀的设计模式,整体提升自己的技术功底深度掌握技术框架:源码看多…

由论文写作到知识教育传承,智者善用,扶AIGC踏新程!

在学术领域中,诚信是不可动摇的基石。但是,令人震惊的事件发生了,竟有学术论文作者将ChatGPT上操作按钮的短语「Regenerate Response」毫无保留地援引到自己的论文中,更令人惊讶的是,审稿编辑竟然未能察觉这一事实&…

EKF例程 matlab

% 不含IMU误差方程的EKF滤波典型程序,适用于多次滤波的第二级 % author:Evand % date: 2023-09-20 % Ver1 clear;clc;close all; global T %% initial T 0.1; %采样率 t [T:T:100]; Q 0.1diag([1,1,1]);wsqrt(Q)randn(size(Q,1),length(t)); R 1diag([1,1,1]);v…

管道和重定向分号-连接符

本文介绍shell脚本常用命令连接符&#xff1a;管道符( | )、重定向( < 、>、>>、2> 、&> )、分号( ; ) 本文内容同微信公众号【凡登】&#xff0c;关注不迷路&#xff0c;学习上高速&#xff0c;欢迎关注共同学习。 1、管道 进程的通信方式之一&#xf…

振弦采集仪应用水坝安全监测的方案

振弦采集仪应用水坝安全监测的方案 随着工业化和城市化的快速发展&#xff0c;水资源的开发和利用越来越广泛。由于水坝在水利工程中起着至关重要的作用&#xff0c;因此对水坝进行安全监测变得越来越必要。为了实现对水坝的安全监测&#xff0c;振弦采集仪可以作为一种有效的…

常见的作物模型有哪些?DSSAT模型、APSIM模型、WOFOST模型与PCSE模型等应用

目录 ①最新DSSAT作物模型建模方法及应用 ②基于Python语言快速批量运行DSSAT模型及交叉融合、扩展应用 ③R语言与作物模型&#xff08;以DSSAT模型为例&#xff09;融合应用 ④WOFOST模型与PCSE模型应用 ⑤基于R语言APSIM模型进阶应用与参数优化、批量模拟 ⑥遥感数据与…

Windows中将tomcat以服务的形式安装,然后在服务进行启动管理

Windows中将tomcat以服务的形式安装,然后在服务进行启动管理 第一步&#xff1a; 在已经安装好的tomcat的bin目录下&#xff1a; 输入cmd&#xff0c;进入命令窗口 安装服务&#xff1a; 输入如下命令&#xff0c;最后是你的服务名&#xff0c;避免中文和特殊字符 service.…

怎样制作一个展会场馆预约小程序

随着互联网的发展&#xff0c;展会行业也逐渐向数字化转型。展会场馆预约小程序作为展会线下向线上的延伸&#xff0c;能够让参展商和观众随时随地进行预约&#xff0c;大大提升了客户的体验。那么&#xff0c;如何制作一个展会场馆预约小程序呢&#xff1f;下面就以乔拓云平台…