【数组】leetcode——移除元素
编号:27. 移除元素
给你一个数组 nums 和一个值 val,你需要 原地 移除所有数值等于 val 的元素,并返回移除后数组的新长度。
不要使用额外的数组空间,你必须仅使用 O(1) 额外空间并「原地」修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
示例 1:
给定 nums = [3,2,2,3], val = 3,
函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。
你不需要考虑数组中超出新长度后面的元素。
示例 2:
给定 nums = [0,1,2,2,3,0,4,2], val = 2,
函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。
思路
首先是数组元素在内存地址中是连续的,不能直接删除,需要覆盖。而且题目说了不需要考虑数组超出新长度后面的元素。因此我们很容易想到暴力解法。
暴力解法
使用两层for循环,外层for循环遍历数组,内层for循环更新数组,当nums[i]==val,将后面的数组元素往前一位进行覆盖,同时数组长度-1。
具体代码如下:
func removeElement(nums []int, val int) int {
length := len(nums)
for i := 0; i < length; i++ {
if nums[i] == val { //找到了目标值,将后续的数组元素往前进行覆盖
for j := i + 1; j < length; j++ {
nums[j-1] = nums[j]
}
i-- //因为数组后续值覆盖了,所以需要在当前位继续进行判断nums[i]?=val
length-- //数组长度-1
}
}
return length
}
可以了解到,暴力解法的时间复杂度为O(n2),空间复杂度为O(1)
下面介绍一种更为便捷的方法,双指针法:「通过一个快指针和慢指针在一个for循环下完成两个for循环的工作」 双指针法在数组和链表的操作中是非常常见的,很多考察数组和链表操作的面试题,都使用双指针法。
双指针法
一开始慢指针slowIndex和快指针fastIndex同时指向数组第0个元素,快指针fastIndex开始遍历数组,如果快指针指向的元素不为val,则nums[slowIndex]=nums[fastIndex],并且slowIndex++。最后返回的slowIndex值就是数组删去元素val的新长度。(这里引用了公众号【代码随想录】的动图,比较方便直观。)
具体代码如下:
func removeElement(nums []int,val int) int{
slowIndex := 0
for fastIndex := 0;fastIndex<len(nums);fastIndex++{
if val != nums[fastIndex]{
nums[slowIndex] = nums[fastIndex]
slowIndex++
}
}
return slowIndex
}
最新文章
- python 解压 压缩包
- 初始Java 第一课程DVD项目
- 用c解决的小题目
- Jenkins离线下载插件,并安装
- 再来一发!DB2 应用程序如何从数据库取数据 Fetch
- SQL脚本循环修改数据库字段类型
- 如何为Kafka集群选择合适的Partitions数量
- spring3定时器简单配置
- iOS开发——开发必备OC篇&;UITableView设置界面完整封装(四)
- 错误:类Byte是公共的,应在名为Byte.java 的文件中声明public class Byte{}一个错误
- BZOJ 3384: [Usaco2004 Nov]Apple Catching 接苹果( dp )
- 设计模式之单一职责原则(SRP)
- .Net高级进阶,WebApi和MVC进行模型验证的时候,教你如何自由控制需要进行验证的字段?
- python爬虫如何爬知乎的话题?
- LeetCode之“动态规划”:Edit Distance
- TS学习随笔(七)->;声明文件
- 免费开源的会计软件 GnuCash 3.4 发布
- H5高德地图获取当前位置
- Adjacent Bit Counts(01组合数)
- Online
热门文章
- ES6箭头函数与this指向
- 修改postman工具的代码生成工具让它锦上添花
- Go语言从入门到放弃(四)
- Educational Codeforces Round 102 (Rated for Div. 2)
- vim 手动添加脚本头部信息
- (一)React Ant Design Pro + .Net5 WebApi:先搞定服务器,顺手装个Nginx
- leetcode 940. 不同的子序列 II (动态规划 ,字符串, hash,好题)
- Web安全之CSRF(跨站请求伪造)
- 【一天一个知识点系列】- Http之状态码
- SAP GUI用颜色区分不同的系统