移除元素
2022/4/28 23:12:40
本文主要是介绍移除元素,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
移除元素
27. 移除元素
给你一个数组 nums 和一个值 val,你需要 原地 移除所有数值等于 val 的元素,并返回移除后数组的新长度。
不要使用额外的数组空间,你必须仅使用 O(1) 额外空间并原地修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
思路
数组中的元素只能覆盖,不能删除
方法1:暴力遍历
用双重for循环遍历,寻找到val时将后续元素向前移一位
方法2:双指针(快慢指针法)
设置两个指针,一个快指针和一个慢指针。
令慢指针在元素非val的时候向前移动,为val的时候停顿,并持续将快指针的指向的值赋予慢指针,覆盖val的值
最后慢指针的值就是数组的长度。
- 复杂度:
- 时间:O(n)
- 空间:O(1)
class Solution { public int removeElement(int[] nums, int val) { //单向双指针法 //一个指针指要删除的数,一个指下一个数 int slowIndex = 0; for (int fastIndex = 0; fastIndex < nums.length; fastIndex++) { //为val值时slowIndex停滞,下一次循环时快指针指向的内容替换慢指针指向的val if (val != nums[fastIndex]) { nums[slowIndex++] = nums[fastIndex]; } } return slowIndex; } }
方法3:相向双指针法
设置左右两个指针:
- 左指针从左向右遍历,找到val值停下
- 右指针从右向左遍历,找到非val值停下
- 将右指针指向的值覆盖val
- 循环,直至循环结束,返回左指针的值或右指针+1
在遍历时,右指针遇到的val值必然超出结果所得到的数组的界限,是要被抛弃的val,不需要进行覆盖操作。到两根指针相遇时,左指针指向数组的后一位,而右指针必然在左指针前一位(循环条件为left<=right),返回值为剩余数组的长度。
class Solution { public int removeElement(int[] nums, int val) { //双向双指针法 //一个指针指要删除的数,一个指不要删除的数 int n = nums.length; int leftIndex = 0, rightIndex = n - 1; while (leftIndex <= rightIndex) { //左指针从左开始找val while (leftIndex <= rightIndex && nums[leftIndex] != val) { ++leftIndex; } //右指针从右开始找非val while (leftIndex <= rightIndex && nums[rightIndex] == val) { --rightIndex; } //把右边的非val数替换到前面的val中,直接忽视末尾的val if (leftIndex < rightIndex) { //替换之后继续遍历 nums[leftIndex++] = nums[rightIndex--]; } } //leftIndex指向末尾的下一个元素,即数组长度;或rightIndex + 1(循环结束条件) return rightIndex + 1; } }
这篇关于移除元素的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-26结对编程到底难不难?答案在这里
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现
- 2024-06-03为什么以及如何要进行架构设计权衡?
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)
- 2024-05-31全网首发!软考2024年5月《软件设计师》真题+解析+答案!(21-30题)