【C++】原地删除有序数组重复元素：两种解法的深度剖析

一、问题描述题目要求给定一个非严格递增排列的整数数组nums需要原地删除重复出现的元素使得每个元素只出现一次并返回删除后数组的新长度。具体要求元素的相对顺序必须保持一致返回唯一元素的数量 k数组的前 k 个元素应包含去重后的唯一数字下标 k-1 之后的元素可以忽略示例cpp输入: nums [1,1,2] 输出: 2, nums [1,2,_] 解释: 函数应返回长度 2原数组的前两个元素修改为 [1,2] 输入: nums [0,0,1,1,1,2,2,3,3,4] 输出: 5, nums [0,1,2,3,4,_,_,_,_,_]二、解法一迭代器与 erase 操作代码实现cppclass Solution { public: int removeDuplicates(vectorint nums) { vectorint:: iterator it nums.begin(); it; // 从第二个元素开始 while(it ! nums.end()) { if((*it) *(it - 1)) // 当前元素与前一个元素相同 { it nums.erase(it); // 删除当前元素 } else { it; // 移动到下一个元素 } } return nums.size(); } };算法分析1. 核心思路使用迭代器遍历数组比较当前元素与前一个元素如果相同使用erase删除当前元素如果不同移动到下一个元素2. 关键细节cpp// 为什么从第二个元素开始 // 第一个元素无需与前面的元素比较没有前面的元素 it; // it 初始指向 nums.begin()it 后指向第二个元素 // 为什么比较 it 和 it-1 // 因为数组已排序重复元素相邻 if((*it) *(it - 1)) // erase 的返回值是什么 // erase 返回指向被删除元素之后元素的迭代器 it nums.erase(it); // 删除后 it 自动指向下一个有效元素3. 执行流程示例text初始: [1,1,2,2,3] ↑ it (指向第二个1) 步骤1: it指向1与前一个1相同 → 删除 → [1,2,2,3] 步骤2: it指向2与前一个1不同 → it → [1,2,2,3] 步骤3: it指向第二个2与前一个2相同 → 删除 → [1,2,3] 步骤4: it指向3与前一个2不同 → it → 到达end 结果: [1,2,3]长度34. 时间复杂度分析最坏情况: O(n²)erase操作需要移动后续所有元素假设删除 n 个元素每次平均移动 n/2 个元素平均情况: O(n²)空间复杂度: O(1)原地操作5. 优缺点优点:代码直观易于理解真正修改了数组大小不需要额外空间缺点:效率低频繁移动元素不适合大数据量不是最优解三、解法二双指针法推荐代码实现cppclass Solution { public: int removeDuplicates(vectorint nums) { if (nums.empty()) return 0; int slow 0; // 慢指针指向已去重部分的末尾 for (int fast 1; fast nums.size(); fast) { // 当快指针指向的元素与慢指针不同时 if (nums[fast] ! nums[slow]) { slow; // 慢指针前进 nums[slow] nums[fast]; // 复制不重复的元素 } // 如果相同快指针继续前进慢指针不动 } return slow 1; // 返回新长度 } };算法分析1. 核心思想使用两个指针快指针fast和慢指针slowslow指向已去重部分的最后一个元素fast遍历整个数组当发现新元素时将其复制到slow1的位置2. 可视化演示text初始状态: [0,0,1,1,1,2,2,3,3,4] s f 步骤1: f1, nums[f]0, nums[s]0 → 相同 → f [0,0,1,1,1,2,2,3,3,4] s f 步骤2: f2, nums[f]1, nums[s]0 → 不同 → s, nums[s]nums[f] [0,1,1,1,1,2,2,3,3,4] s f 步骤3: f3, nums[f]1, nums[s]1 → 相同 → f [0,1,1,1,1,2,2,3,3,4] s f 步骤4: f4, nums[f]1, nums[s]1 → 相同 → f [0,1,1,1,1,2,2,3,3,4] s f 步骤5: f5, nums[f]2, nums[s]1 → 不同 → s, nums[s]nums[f] [0,1,2,1,1,2,2,3,3,4] s f ... 以此类推最终得到 [0,1,2,3,4]3. 时间复杂度分析时间复杂度: O(n)只需遍历数组一次每个元素最多被访问两次空间复杂度: O(1)只使用两个指针变量4. 边界情况处理cpp// 空数组 if (nums.empty()) return 0; // 单元素数组 // 直接返回1无需任何操作 // 所有元素都相同 // slow始终为0返回1四、两种解法的对比性能对比表特性迭代器erase法双指针法时间复杂度O(n²)O(n)空间复杂度O(1)O(1)是否真正删除是否只是覆盖代码复杂度中等简单执行效率低高适用场景小数据量所有场景内存操作对比cpp// 方法一erase操作的内存变化 [1,1,2,2,3] // 原始 [1,2,2,3] // 删除第一个重复1移动后面3个元素 [1,2,3] // 删除重复2移动后面1个元素 // 总共移动4个元素 // 方法二双指针法的内存变化 [1,1,2,2,3] // 原始 [1,2,2,3,3] // 第一次复制fast2, slow1 [1,2,3,3,3] // 第二次复制fast4, slow2 // 没有元素移动只有覆盖操作五、常见错误与陷阱错误1迭代器越界cpp// 错误的写法 while(it ! nums.end()) { if(*(it) *(it 1)) { // 当it指向最后一个元素时it1越界 it nums.erase(it); } it; }错误2逻辑错误cpp// 错误的写法 while(it ! nums.end()) { if((*it) *(it - 1)) { nums.erase(it); // 没有接收返回值it失效 } it; // 使用失效的迭代器 }错误3未处理空数组cpp// 需要处理空数组 if (nums.empty()) return 0;六、扩展思考1. 如果数组未排序怎么办cpp// 需要先排序但会改变相对顺序 sort(nums.begin(), nums.end()); // 然后再去重2. 如果允许每个元素最多出现两次怎么办cppclass Solution { public: int removeDuplicates(vectorint nums) { if (nums.size() 2) return nums.size(); int slow 2; // 从第三个元素开始 for (int fast 2; fast nums.size(); fast) { // 比较当前元素与slow-2位置的元素 if (nums[fast] ! nums[slow - 2]) { nums[slow] nums[fast]; slow; } } return slow; } };3. 如果要去重并保留原顺序未排序数组cpp// 使用哈希表记录已出现元素 int removeDuplicatesUnordered(vectorint nums) { unordered_setint seen; int slow 0; for (int fast 0; fast nums.size(); fast) { if (seen.find(nums[fast]) seen.end()) { seen.insert(nums[fast]); nums[slow] nums[fast]; slow; } } return slow; }七、实际应用场景1. 数据库查询结果去重sql-- SQL中的DISTINCT类似于数组去重 SELECT DISTINCT column_name FROM table_name;2. 日志分析去除重复的日志条目统计唯一IP地址分析用户唯一访问量3. 数据清洗去除重复记录整理有序数据集准备机器学习训练数据4. 内存优化减少内存占用提高缓存效率优化数据处理流水线八、性能测试测试代码cppvoid testPerformance() { // 生成测试数据100万个有序整数有大量重复 vectorint nums; for (int i 0; i 1000000; i) { nums.push_back(i / 100); // 每个数字重复100次 } vectorint nums1 nums; vectorint nums2 nums; // 测试方法一 auto start chrono::high_resolution_clock::now(); Solution().removeDuplicatesErase(nums1); auto end chrono::high_resolution_clock::now(); auto duration1 chrono::duration_castchrono::milliseconds(end - start); // 测试方法二 start chrono::high_resolution_clock::now(); Solution().removeDuplicatesTwoPointers(nums2); end chrono::high_resolution_clock::now(); auto duration2 chrono::duration_castchrono::milliseconds(end - start); cout 方法一erase用时: duration1.count() ms endl; cout 方法二双指针用时: duration2.count() ms endl; }预期结果text方法一erase用时: 约5000ms 方法二双指针用时: 约10ms九、总结与建议1. 算法选择建议面试场景优先展示双指针法体现算法优化思维小数据量两种方法都可erase法代码更直观大数据量必须使用双指针法工程实践优先考虑效率和可维护性2. 学习要点理解原地操作的含义和限制掌握迭代器的正确使用方法熟练应用双指针技巧分析算法的时间空间复杂度3. 类似题目推荐删除排序数组中的重复项 II每个元素最多出现两次移动零将0移动到末尾保持非零元素顺序移除元素移除特定值返回新长度合并两个有序数组4. 最终建议在实际编程和面试中双指针法是解决这类问题的首选。它不仅效率高而且思路清晰代码简洁。理解并掌握这种思想能够解决一大类数组操作问题。记住好的算法应该是高效且优雅的双指针法正是这样的典范。