1. 问题背景与需求分析在算法面试和日常编程中处理有序数组的去重操作是一个经典问题。LeetCode第26题删除有序数组中的重复项要求我们原地修改输入数组使得每个元素只出现一次并返回新的长度。这个问题看似简单但考察了几个关键编程能力对数组数据结构的理解双指针算法的应用原地修改数组的技巧边界条件的处理能力实际业务场景中类似操作也很常见。比如处理日志数据时去除连续重复条目数据库查询结果去重时间序列数据的清洗2. 问题描述与示例给定一个非严格递增排列的数组nums原地删除重复出现的元素使每个元素只出现一次。返回删除后数组的新长度。要求必须原地修改输入数组使用O(1)额外空间元素的相对顺序必须保持一致示例1 输入nums [1,1,2] 输出2, nums [1,2,_] 解释函数应返回长度2原数组前两个元素修改为1和2示例2 输入nums [0,0,1,1,1,2,2,3,3,4] 输出5, nums [0,1,2,3,4,,,,,_]3. 双指针解法详解3.1 基本思路最直观的解法是使用双指针技术慢指针(slow)指向当前唯一元素的最后一个位置快指针(fast)遍历数组寻找下一个不重复元素当找到不重复元素时将其复制到slow1位置然后slow前进这种方法的优势在于时间复杂度O(n)只需遍历一次数组空间复杂度O(1)只使用了常数个额外变量保持了元素的原始顺序3.2 代码实现def removeDuplicates(nums): if not nums: return 0 slow 0 for fast in range(1, len(nums)): if nums[fast] ! nums[slow]: slow 1 nums[slow] nums[fast] return slow 13.3 执行过程分析以nums [0,0,1,1,1,2,2,3,3,4]为例初始状态 slow0, fast1 nums[1]0 nums[0]0 → 不操作fast2: nums[2]1 ! nums[0]0 → slow1, nums[1]1 数组变为[0,1,1,1,1,2,2,3,3,4]fast3: nums[3]1 nums[1]1 → 不操作fast4: nums[4]1 nums[1]1 → 不操作fast5: nums[5]2 ! nums[1]1 → slow2, nums[2]2 数组变为[0,1,2,1,1,2,2,3,3,4]fast6: nums[6]2 nums[2]2 → 不操作fast7: nums[7]3 ! nums[2]2 → slow3, nums[3]3 数组变为[0,1,2,3,1,2,2,3,3,4]fast8: nums[8]3 nums[3]3 → 不操作fast9: nums[9]4 ! nums[3]3 → slow4, nums[4]4 最终数组[0,1,2,3,4,2,2,3,3,4] 返回长度54. 边界条件与特殊情况处理4.1 空数组处理当输入数组为空时应直接返回0。这是最容易忽略的边界情况。if not nums: return 04.2 单元素数组数组只有一个元素时无需任何操作直接返回1。4.3 全相同元素数组如nums [1,1,1,1]应返回1数组变为[1,,,_]4.4 已去重数组如nums [1,2,3,4]应返回4数组保持不变5. 算法复杂度分析时间复杂度O(n)只需一次遍历数组每个元素最多被访问一次空间复杂度O(1)只使用了slow和fast两个额外变量6. 变种问题与扩展6.1 允许最多保留k个重复项LeetCode第80题是此问题的扩展要求每个元素最多出现两次。通用解法def removeDuplicates(nums, k2): if len(nums) k: return len(nums) slow k for fast in range(k, len(nums)): if nums[fast] ! nums[slow - k]: nums[slow] nums[fast] slow 1 return slow6.2 无序数组去重如果数组无序可以使用哈希表记录已出现元素def removeDuplicates(nums): seen set() slow 0 for fast in range(len(nums)): if nums[fast] not in seen: seen.add(nums[fast]) nums[slow] nums[fast] slow 1 return slow但这种方法空间复杂度为O(n)不符合本题要求。6.3 返回新数组而非修改原数组如果允许返回新数组可以直接使用集合def removeDuplicates(nums): return list(set(nums))但会丢失元素顺序且空间复杂度为O(n)7. 实际应用场景7.1 数据库查询结果去重SELECT DISTINCT column FROM table在内存中处理时可能需要类似的去重算法7.2 日志处理去除连续的重复日志条目减少存储空间7.3 时间序列数据清洗去除传感器采集的重复数据点8. 常见错误与调试技巧8.1 数组越界错误忘记检查数组是否为空直接访问nums[0]会导致错误8.2 逻辑错误错误地将slow指针初始化为1导致第一个元素被跳过8.3 测试用例建议应测试以下情况空数组单元素数组全相同元素数组已去重数组常规有重复数组8.4 调试技巧可以在循环中加入打印语句观察指针移动和数组变化print(fslow{slow}, fast{fast}, nums{nums})9. 性能优化与语言特性9.1 Python中的优化在Python中列表操作可能较慢。对于大型数组可以考虑使用numpy数组import numpy as np def removeDuplicates(nums): nums np.array(nums) if len(nums) 0: return 0 slow 0 for fast in range(1, len(nums)): if nums[fast] ! nums[slow]: slow 1 nums[slow] nums[fast] return slow 19.2 C实现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]) { nums[slow] nums[fast]; } } return slow 1; }9.3 Java实现public int removeDuplicates(int[] nums) { if (nums.length 0) return 0; int slow 0; for (int fast 1; fast nums.length; fast) { if (nums[fast] ! nums[slow]) { nums[slow] nums[fast]; } } return slow 1; }10. 面试技巧与注意事项10.1 面试官可能问的问题为什么选择双指针解法如何处理边界条件时间复杂度和空间复杂度是多少如何测试你的代码如果数组很大如何优化10.2 回答技巧先明确问题要求和约束条件解释算法思路画图说明指针移动主动讨论边界条件和测试用例分析复杂度讨论优化可能性10.3 代码风格建议添加有意义的变量名slow/fast比i/j更好添加必要的注释先处理边界条件保持代码简洁但可读11. 相关题目推荐LeetCode 27 - 移除元素LeetCode 80 - 删除有序数组中的重复项 IILeetCode 283 - 移动零LeetCode 844 - 比较含退格的字符串LeetCode 977 - 有序数组的平方12. 学习资源与进阶《算法导论》 - 基础算法部分《编程珠玑》 - 数组处理技巧LeetCode探索卡片 - 数组与字符串双指针算法专题原地算法(in-place algorithm)研究在实际刷题过程中我发现理解双指针的核心思想比记忆特定解法更重要。这个问题的关键在于认识到我们可以利用数组的有序性通过比较相邻元素来识别重复项。这种模式可以推广到许多其他数组处理问题中。
1. 问题背景与需求分析在算法面试和日常编程中处理有序数组的去重操作是一个经典问题。LeetCode第26题删除有序数组中的重复项要求我们原地修改输入数组使得每个元素只出现一次并返回新的长度。这个问题看似简单但考察了几个关键编程能力对数组数据结构的理解双指针算法的应用原地修改数组的技巧边界条件的处理能力实际业务场景中类似操作也很常见。比如处理日志数据时去除连续重复条目数据库查询结果去重时间序列数据的清洗2. 问题描述与示例给定一个非严格递增排列的数组nums原地删除重复出现的元素使每个元素只出现一次。返回删除后数组的新长度。要求必须原地修改输入数组使用O(1)额外空间元素的相对顺序必须保持一致示例1 输入nums [1,1,2] 输出2, nums [1,2,_] 解释函数应返回长度2原数组前两个元素修改为1和2示例2 输入nums [0,0,1,1,1,2,2,3,3,4] 输出5, nums [0,1,2,3,4,,,,,_]3. 双指针解法详解3.1 基本思路最直观的解法是使用双指针技术慢指针(slow)指向当前唯一元素的最后一个位置快指针(fast)遍历数组寻找下一个不重复元素当找到不重复元素时将其复制到slow1位置然后slow前进这种方法的优势在于时间复杂度O(n)只需遍历一次数组空间复杂度O(1)只使用了常数个额外变量保持了元素的原始顺序3.2 代码实现def removeDuplicates(nums): if not nums: return 0 slow 0 for fast in range(1, len(nums)): if nums[fast] ! nums[slow]: slow 1 nums[slow] nums[fast] return slow 13.3 执行过程分析以nums [0,0,1,1,1,2,2,3,3,4]为例初始状态 slow0, fast1 nums[1]0 nums[0]0 → 不操作fast2: nums[2]1 ! nums[0]0 → slow1, nums[1]1 数组变为[0,1,1,1,1,2,2,3,3,4]fast3: nums[3]1 nums[1]1 → 不操作fast4: nums[4]1 nums[1]1 → 不操作fast5: nums[5]2 ! nums[1]1 → slow2, nums[2]2 数组变为[0,1,2,1,1,2,2,3,3,4]fast6: nums[6]2 nums[2]2 → 不操作fast7: nums[7]3 ! nums[2]2 → slow3, nums[3]3 数组变为[0,1,2,3,1,2,2,3,3,4]fast8: nums[8]3 nums[3]3 → 不操作fast9: nums[9]4 ! nums[3]3 → slow4, nums[4]4 最终数组[0,1,2,3,4,2,2,3,3,4] 返回长度54. 边界条件与特殊情况处理4.1 空数组处理当输入数组为空时应直接返回0。这是最容易忽略的边界情况。if not nums: return 04.2 单元素数组数组只有一个元素时无需任何操作直接返回1。4.3 全相同元素数组如nums [1,1,1,1]应返回1数组变为[1,,,_]4.4 已去重数组如nums [1,2,3,4]应返回4数组保持不变5. 算法复杂度分析时间复杂度O(n)只需一次遍历数组每个元素最多被访问一次空间复杂度O(1)只使用了slow和fast两个额外变量6. 变种问题与扩展6.1 允许最多保留k个重复项LeetCode第80题是此问题的扩展要求每个元素最多出现两次。通用解法def removeDuplicates(nums, k2): if len(nums) k: return len(nums) slow k for fast in range(k, len(nums)): if nums[fast] ! nums[slow - k]: nums[slow] nums[fast] slow 1 return slow6.2 无序数组去重如果数组无序可以使用哈希表记录已出现元素def removeDuplicates(nums): seen set() slow 0 for fast in range(len(nums)): if nums[fast] not in seen: seen.add(nums[fast]) nums[slow] nums[fast] slow 1 return slow但这种方法空间复杂度为O(n)不符合本题要求。6.3 返回新数组而非修改原数组如果允许返回新数组可以直接使用集合def removeDuplicates(nums): return list(set(nums))但会丢失元素顺序且空间复杂度为O(n)7. 实际应用场景7.1 数据库查询结果去重SELECT DISTINCT column FROM table在内存中处理时可能需要类似的去重算法7.2 日志处理去除连续的重复日志条目减少存储空间7.3 时间序列数据清洗去除传感器采集的重复数据点8. 常见错误与调试技巧8.1 数组越界错误忘记检查数组是否为空直接访问nums[0]会导致错误8.2 逻辑错误错误地将slow指针初始化为1导致第一个元素被跳过8.3 测试用例建议应测试以下情况空数组单元素数组全相同元素数组已去重数组常规有重复数组8.4 调试技巧可以在循环中加入打印语句观察指针移动和数组变化print(fslow{slow}, fast{fast}, nums{nums})9. 性能优化与语言特性9.1 Python中的优化在Python中列表操作可能较慢。对于大型数组可以考虑使用numpy数组import numpy as np def removeDuplicates(nums): nums np.array(nums) if len(nums) 0: return 0 slow 0 for fast in range(1, len(nums)): if nums[fast] ! nums[slow]: slow 1 nums[slow] nums[fast] return slow 19.2 C实现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]) { nums[slow] nums[fast]; } } return slow 1; }9.3 Java实现public int removeDuplicates(int[] nums) { if (nums.length 0) return 0; int slow 0; for (int fast 1; fast nums.length; fast) { if (nums[fast] ! nums[slow]) { nums[slow] nums[fast]; } } return slow 1; }10. 面试技巧与注意事项10.1 面试官可能问的问题为什么选择双指针解法如何处理边界条件时间复杂度和空间复杂度是多少如何测试你的代码如果数组很大如何优化10.2 回答技巧先明确问题要求和约束条件解释算法思路画图说明指针移动主动讨论边界条件和测试用例分析复杂度讨论优化可能性10.3 代码风格建议添加有意义的变量名slow/fast比i/j更好添加必要的注释先处理边界条件保持代码简洁但可读11. 相关题目推荐LeetCode 27 - 移除元素LeetCode 80 - 删除有序数组中的重复项 IILeetCode 283 - 移动零LeetCode 844 - 比较含退格的字符串LeetCode 977 - 有序数组的平方12. 学习资源与进阶《算法导论》 - 基础算法部分《编程珠玑》 - 数组处理技巧LeetCode探索卡片 - 数组与字符串双指针算法专题原地算法(in-place algorithm)研究在实际刷题过程中我发现理解双指针的核心思想比记忆特定解法更重要。这个问题的关键在于认识到我们可以利用数组的有序性通过比较相邻元素来识别重复项。这种模式可以推广到许多其他数组处理问题中。
