删除有序数组中的重复项
848 字
4 分钟
删除有序数组中的重复项
题目链接：26. 删除有序数组中的重复项 - 力扣（LeetCode）
- 难度：简单
- 标签：数组、双指针
题目描述
Note
原题说明：
给你一个 非严格递增排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数。
判定标准：
系统会检查 nums 的前 k 个元素是否为去重后的有序数字。
示例
- 输入：
nums = [1,1,2]-> 输出：2, nums = [1,2,_] - 输入：
nums = [0,0,1,1,1,2,2,3,3,4]-> 输出：5, nums = [0,1,2,3,4,_,_,_,_,_]
方案一：标记替换法（探索尝试）
核心思路：
遍历数组，如果发现当前元素与前一个元素相同，就将其标记为一个特殊的“空值”（如 EMPTY = 10001），最后再通过一遍遍历将所有非空值搬到数组前端。
源码实现
class Solution {public: int removeDuplicates(vector<int>& nums) { if (nums.empty()) return 0; const int EMPTY = 10001; int n = nums.size();
// 1. 标记重复项 for (int i = 1; i < n; ++i) { if (nums[i] == nums[i - 1]) nums[i] = EMPTY; }
// 2. 集中非空项到前端 int write = 0; for (int read = 0; read < n; ++read) { if (nums[read] != EMPTY) { nums[write++] = nums[read]; } } return write; }};逻辑缺陷
虽然思路清晰，但这种“先标记再移动”的做法对于三个及以上重复项（如 [1, 1, 1]）会失效。因为标记完第二个 1 后，第三个 1 与已经变成 EMPTY 的前驱相比，会被误认为是不重复的。
方案二：快慢指针法（标准解法）
核心思路：
使用两个指针：read（快指针）负责扫描原数组，write（慢指针）负责记录当前不重复序列的末尾。只有当快指针发现一个与慢指针不同的新元素时，才将其写入慢指针的下一个位置。
源码实现
class Solution {public: int removeDuplicates(vector<int>& nums) { if (nums.empty()) return 0;
int write = 0; // 慢指针：指向当前最新不重复元素 for (int read = 1; read < nums.size(); ++read) { // 发现新元素（不同于当前慢指针指向的值） if (nums[read] != nums[write]) { nums[++write] = nums[read]; // 搬移到前端 } } return write + 1; // 长度 = 下标 + 1 }};复杂度分析
- 时间复杂度：。其中 是数组的长度。我们只需进行一次线性扫描。
- 空间复杂度：。我们直接在原数组上进行修改，没有使用额外空间。
方案三：一行代码（STL 威力）
在 C++ 中，这种原地去重操作其实已经封装在 <algorithm> 库的 std::unique 函数中了。
class Solution {public: int removeDuplicates(vector<int>& nums) { // unique 返回去重后“剩余区间”的起始迭代器 return unique(nums.begin(), nums.end()) - nums.begin(); }};总结
- 原地修改 (In-place)：题目强调不能创建新数组，因此双指针是处理此类问题的核心技巧。
- 边界处理：
- 空数组必须提前返回
0。 - 指针初始值：
write从0开始，read从1开始。
- 空数组必须提前返回
- 易错点：最终返回的是长度（下标 + 1），而不是慢指针的下标。
Tip
以后遇到“有序数组原地去重、移动元素”等问题，第一时间要在脑海中建立出“快慢指针”的双轨运行模型！
文章分享
如果这篇文章对你有帮助，欢迎分享给更多人！
最后更新于 2025-10-09，距今已过 202 天
部分内容可能已过时
相关文章 智能推荐
1
合并两个有序数组
算法 力扣第88题：合并两个有序数组。从正向合并的繁琐到逆向双指针的极简之美，实现 $O(m+n)$ 的高效原地合并。
2
移除元素
算法 力扣第27题：原地移除数组中所有等于 val 的元素。深入理解快慢指针在乱序数组中的灵活应用。
3
删除排序链表中的重复元素
算法 力扣第83题：删除排序链表中的重复元素。深入理解链表指针操作，掌握“跳过”重复节点的优雅技巧。
4
两数之和
算法 力扣第1题：两数之和的暴力解法与哈希表优化解法分析。
5
回文数
算法 力扣第9题：回文数的判断。从暴力取余到“反转一半”的思路演进，以及字符串双指针解法。
随机文章 随机推荐
评论区
欢迎来到我的博客！
音乐
暂未播放
0:00 0:00
119
11
346
226,548
0 天
0 天前