当前位置: 首页 > news >正文

27. 移除元素 暴力+快慢指针+相向双指针

27. 移除元素

1、暴力

解题过程

外层循环遍历nums数组,当遇到等于val的元素时,进入内层循环将后续元素均前移一位,覆盖前一个元素。

时间复杂度: O(n^2)

空间复杂度: O(1)

class Solution {public int removeElement(int[] nums, int val) {int n = nums.length;for (int i = 0; i < n; i++) { // 外层循环遍历数组元素if (nums[i] == val) {for (int j = i + 1; j < n; j++) { //内层循环删除等于val的元素(后续元素均前移一位)nums[j - 1] = nums[j];}i--; // nums[i]已被新元素覆盖,尚未判断新元素是否等于valn--; // 未被遍历的元素均前移一位,更新遍历区间的右边界}}return n;}
}

2、快慢指针

解题过程
遍历数组,遇到等于val的元素就向前追加,覆盖前面的旧元素,最终所有有效元素都位于前面。
快指针在旧数组中找非目标元素,然后赋值给慢指针指向的新数组
对于移除元素可以理解为,拿右边 right 所指元素填补左边 left 所指元素的坑,坑就是 left 从左到右遍历过程中遇要的需要删除的元素。

时间复杂度: O(n)
空间复杂度: O(1)

class Solution {public int removeElement(int[] nums, int val) {int count = 0; // 记录有效元素个数for (int i = 0; i < nums.length; i++) {if (nums[i] != val) nums[count++] = nums[i]; // 有效元素追加到前面}return count;}
}

3、相向双指针

解题过程
left,right初始化为数组的左、右边界。若nums[left] == val,left 位置的元素需要被覆盖,直接用 right 所指元素覆盖,更新 right 指向下一个可用于(等于val、不等于val都可以)覆盖的元素;若nums[left] != val,left 位置的元素不用被覆盖 更新 left 指向下一个新元素。重复上面的过程,直至 left > right。

时间复杂度: O(n)
空间复杂度: O(1)

class Solution {public int removeElement(int[] nums, int val) {int left = 0;int right = nums.length - 1;while (left <= right) {if (nums[left] == val) { // left所指元素需要被覆盖nums[left] = nums[right]; // 直接将right所指元素覆盖到left位置,未判断该元素是否等于val,左边界left 不动,在下一次循环判断该元素right--; // 更新右边界,right 指向下一个用来覆盖的元素} else {left++;}}return left;}
}
http://www.hskmm.com/?act=detail&tid=29423

相关文章:

  • ST表学习笔记
  • 谈一类易实现的非四毛子线性 RMQ
  • 我们学会在具体情境中做出恰当判断
  • 编译安装nginx
  • AutoGCL——AutoGCL: automated graph contrastive learning via learnable view generators
  • 【教程】无需第三方应用,Windows自带邮箱如何绑定QQ邮箱等第三方邮箱
  • 2025婚纱摄影影楼权威推荐榜:专业团队与创意拍摄打造梦幻婚礼
  • 为什么40岁后的快乐消失了
  • 分布式结构化存储系统-HBase访问方式
  • 【Azure APIM】自建网关(self-host gateway)收集请求的Header和Body内容到日志中的办法
  • [JAVA]JDK多版本设置
  • Google Veo3生成跳舞视频
  • 【PolarCTF】stackof
  • 新生赛 F,H,J 题解
  • pycharm跑python项目易出错的困难
  • 双端队列的0-1BFS
  • Python psycopg2 类库使用学习总结
  • [GenAI] RAG架构演进
  • 24NOIP游记——彼时彼刻
  • 嵌入式-C++面经1
  • 合并区间 - MKT
  • 如何防止员工向第三方 AI 泄露数据?滤海 AI DLP 全方位技术防护方案解析
  • 20232322 2025-2026-1 《网络与系统攻防技术》实验一实验报告
  • 实验1 现代c++编程初体验
  • 冬天快乐
  • P2441M 见过的 tricks
  • 企业大数据战略定位
  • OpenAI加码个性化消费AI技术布局
  • 线性回归 C++ 实现
  • 内存分区