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

1. 题目26. 删除有序数组中的重复项 - 力扣LeetCode题目描述给你一个升序排列的数组nums请你原地删除重复出现的元素使每个元素只出现一次 返回删除后数组的新长度。元素的相对顺序应当保持一致。不要使用额外的数组空间必须在 (O(1)) 额外空间条件下原地修改输入数组。无需考虑数组中超出新长度后面的元素。示例输入nums [1,1,2]输出2nums [1,2,] 输入nums [0,0,1,1,1,2,2,3,3,4] 输出5nums [0,1,2,3,4,,,,,]约束(1 nums.length 3 * 10^4)(-10^4 nums[i] 10^4)nums已按升序排列2. 最佳解题思路描述快慢双指针最优快慢指针定义slow慢指针指向当前有效数组最后一位初始为 0fast快指针遍历全部数组逐个寻找新的不重复数字遍历逻辑快指针遇到和nums[slow]不相等的元素说明是新唯一值slow拓展有效区间把新值覆盖到nums[slow]最终有效长度为slow 1。优势时间 (O(n))仅一次遍历空间 (O(1))无 erase、无数组移位有序数组去重通用模板面试首选。3. 我的可优化代码逻辑能 AC但性能差class Solution { public: int removeDuplicates(vectorint nums) { int nnums.size(); int m n; for(int i0;in-1;i){ if(nums[i]nums[i1]){ nums.erase(nums.begin()i); n--; i--; m--; } } return m; } };代码说明逻辑正确性发现相邻重复元素就 erase 删除数组长度 n 同步缩减i 回退重新判断当前位置m 记录最终长度能通过所有用例。核心缺陷 优化点vectorerase会让删除点后所有元素整体前移单次 erase 时间 (O(n))嵌套循环总时间复杂度 (O(n^2))数据量大时超时频繁修改数组长度、回退 i代码冗余、可读性差额外变量 m、n 重复记录长度无必要。4. 最优标准代码快慢双指针class Solution { public: int removeDuplicates(vectorint nums) { int slow 0; for (int fast 1; fast nums.size(); fast) { if (nums[fast] ! nums[slow]) { slow; nums[slow] nums[fast]; } } return slow 1; } };5. 总结你的 erase 暴力删除写法可以通过测试但时间效率极低面试不推荐有序数组原地去重标准解法是快慢双指针一次遍历无数组删除操作核心规律慢指针保存唯一值末尾快指针找新值不同则拓展有效区间返回长度切记slow 1slow 是下标不是长度。6. 相关知识拓展拓展 1同类模板联动LeetCode27 移除元素、26 有序去重、283 移动零共享快慢指针思想快指针筛选有效元素慢指针维护原地结果数组。拓展 2vector erase 性能坑vector 是连续内存中间删除元素必须移动后方所有元素算法题中应尽量避免循环内频繁 erase改用双指针覆盖赋值替代删除。拓展 3拓展变形保留最多 2 个重复项 LC80仅微调判断逻辑快慢指针框架不变int removeDuplicates(vectorint nums) { int slow 1; for(int fast 2; fast nums.size(); fast){ if(nums[fast] ! nums[slow-1]){ slow; nums[slow] nums[fast]; } } return slow1; }拓展 4复杂度对比erase 暴力写法时间 (O(n^2))空间 (O(1))快慢指针最优解时间 (O(n))空间 (O(1))。