LeetCode 27 移除元素

1. 题目27. 移除元素 - 力扣LeetCode题目描述给你一个数组nums和一个值val你需要原地移除所有数值等于val的元素并返回移除后数组的新长度。不要使用额外的数组空间你必须仅使用 (O(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,4,0,3,,,_]约束(0 nums.length 100)(0 nums[i] 50)(0 val 100)2. 最佳解题思路描述快慢双指针本题标准最优定义快慢指针fast快指针遍历整个数组逐个检查当前元素slow慢指针指向有效数组待填充位置记录不等于 val 的元素存放下标遍历逻辑若nums[fast] ! val说明是保留元素把值赋给nums[slow]慢指针后移若等于 val直接跳过慢指针不动遍历结束后slow的数值就是新数组长度直接返回。优势时间复杂度 (O(n))仅一次遍历数组空间复杂度 (O(1))仅两个临时变量原地修改无额外容器代码极简、逻辑清晰是数组原地去重 / 移除指定值通用模板。3. 我的可优化代码当前代码无逻辑错误是标准最优解仅补充优化小细节class Solution { public: int removeElement(vectorint nums, int val) { int slow 0; for (int fast 0; fast nums.size(); fast) { if (val ! nums[fast]) { nums[slow] nums[fast]; slow; } } return slow; } };代码说明正确性代码逻辑完全正确能通过全部测试用例属于本题最优写法无逻辑 bug可优化小细节不影响 AC仅优化拷贝操作当前写法存在不必要赋值当slow fast时前面没有待删除元素nums[slow] nums[fast]是自身赋值可加判断跳过if (val ! nums[fast]) { if(slow ! fast) nums[slow] nums[fast]; slow; }数组全为保留元素时减少重复赋值性能微提升。4. 最优标准代码你原版行业通用最简版class Solution { public: int removeElement(vectorint nums, int val) { int slow 0; for (int fast 0; fast nums.size(); fast) { if (nums[fast] ! val) { nums[slow] nums[fast]; } } return slow; } };5. 总结快慢双指针是原地移除元素核心模板本题代码无错误、效率最优面试直接写核心规则快指针负责检索慢指针负责维护有效数组返回值是慢指针最终数值不需要额外计算长度题目不要求尾部元素清零无需额外操作。6. 相关知识拓展拓展 1同类快慢指针数组题型模板LeetCode 26 删除有序数组重复项、LeetCode 283 移动零完全复用快慢指针思想快指针遍历筛选有效元素慢指针存放结果。拓展 2另一种解法首尾双指针适合删除元素很多的场景左右指针左找待删除值、右找保留值交换后收缩区间减少数组赋值次数class Solution { public: int removeElement(vectorint nums, int val) { int left 0, right nums.size() - 1; while(left right){ if(nums[left] val){ swap(nums[left], nums[right]); right--; }else{ left; } } return left; } };特点会打乱数组原有顺序题目允许顺序改变时可用。拓展 3复杂度对比快慢指针你的写法(O(n)) 时间(O(1)) 空间保留原数组顺序首尾交换双指针(O(n)) 时间(O(1)) 空间数组顺序打乱暴力 erase嵌套循环 erase(O(n^2)) 时间效率极低不推荐面试。拓展 4快慢指针通用记忆口诀快指针全遍历慢指针存有效不等目标就留存慢指针自增记长度。