LeetCode 80 删除有序数组中的重复项 II

1. 题目80. 删除有序数组中的重复项 II - 力扣LeetCode题目描述给你一个有序数组nums请你原地删除重复出现的元素使每个元素最多出现两次返回删除后数组的新长度。不要使用额外的数组空间必须在 (O(1)) 额外空间并原地修改输入数组。元素的相对顺序应该保持一致。无需考虑数组超出新长度后的部分。示例输入nums [1,1,1,2,2,3]输出5nums [1,1,2,2,3,] 输入nums [0,0,1,1,1,1,2,3,3] 输出7nums [0,0,1,1,2,3,3,,_]约束(1 nums.length 3*10^4)(-10^4 nums[i] 10^4)nums已按升序排列2. 最佳解题思路描述快慢指针通用模板本题最优核心规则有序数组允许同一个数字最多保留 2 个快慢指针定义r慢指针下一个可填充的有效位置初始为 2前两个数字天然合法直接保留l快指针遍历全部数组从下标 2 开始向后扫描判断逻辑对比当前快指针值nums[l]和有效区间倒数第二个值nums[r-2]不相等说明当前数字出现次数≤2是合法元素覆盖到nums[r]慢指针右移相等说明当前数字已经存在两个直接跳过遍历结束后r即为有效数组长度直接返回。优势时间复杂度 (O(n))仅单次遍历空间复杂度 (O(1))原地赋值无 erase、无额外容器可拓展通用最多保留 k 个重复项只需把初始 r、对比下标改成 k。3. 我的可优化代码逻辑完全正确是标准最优解仅微小细节优化class Solution { public: int removeDuplicates(vectorint nums) { int nnums.size(); if(n2){ return n; } int r 2; for(int l r;ln;l){ if(nums[l]!nums[r-2]){ nums[r]nums[l]; } } return r; } };代码说明正确性逻辑无任何 bug能通过全部测试用例是行业标准最优写法可优化小细节边界判断if(n2)可以省略数组长度 0/1 时for 循环不会执行直接 return r2 会出错因此该判断必须保留变量名语义优化r改名为slow、l改名为fast和 26、27 题命名统一方便记忆循环简写nums[slow] nums[fast]压缩一行。4. 标准规范版代码统一快慢指针命名class Solution { public: int removeDuplicates(vectorint nums) { int n nums.size(); if (n 2) return n; int slow 2; for (int fast 2; fast n; fast) { if (nums[fast] ! nums[slow - 2]) { nums[slow] nums[fast]; } } return slow; } };5. 总结你的代码思路、实现完全正确是本题最优解法面试可直接书写核心判断记忆点最多保留 2 个就和slow-2对比初始慢指针从 2 开始前两个数字一定合法无需校验有序数组限制是该解法成立的前提无序数组不能使用此模板无 erase、无嵌套循环性能远优于暴力删除方案。6. 相关知识拓展拓展 1通用模板 —— 最多保留 k 个重复元素将本题逻辑泛化任意 k 都适用int removeDuplicates(vectorint nums, int k) { int n nums.size(); if (n k) return n; int slow k; for (int fast k; fast n; fast) { if (nums[fast] ! nums[slow - k]) { nums[slow] nums[fast]; } } return slow; }LC26最多保留 1 个k1slow 初始 1对比 slow-1LC80最多保留 2 个k2slow 初始 2对比 slow-2。拓展 2暴力 erase 对比不推荐循环 erase 删除第三个及以后重复数字时间复杂度 (O(n^2))大数据超时int removeDuplicates(vectorint nums) { for(int i2;inums.size();i){ if(nums[i]nums[i-2]){ nums.erase(nums.begin()i); i--; } } return nums.size(); }拓展 3同类快慢指针题目汇总LC27 移除指定元素LC26 有序数组去重最多 1 个LC80 有序数组去重最多 2 个LC283 移动零全部遵循fast 遍历筛选slow 维护有效数组。拓展 4复杂度对比快慢指针最优解(O(n)) 时间(O(1)) 空间erase 暴力删除(O(n^2)) 时间(O(1)) 空间。