问题描述
给定一个有序的整数数组，我们需要原地移除所有重复元素，使得每个元素只出现一次，并返回新数组的长度。要求不使用额外的数组空间，空间复杂度为O(1)。
示例：
输入：nums = [1,1,2,2,3,4,4,5] 输出：5, nums = [1,2,3,4,5,...]
方法一：HashSet
HashSet是Java集合框架中的一个类，它实现了Set接口，底层基于哈希表实现。HashSet的核心特性是不允许重复元素，且不保证元素的顺序。
代码实现
import java.util.HashSet; import java.util.Iterator; public class HashSetSolution { public int removeDuplicates(int[] nums) { // 边界条件检查 if (nums == null || nums.length == 0) { return 0; } // 创建HashSet存储唯一元素 HashSet<Integer> uniqueSet = new HashSet<>(); // 遍历原数组，将元素添加到HashSet中 // HashSet会自动去重，重复元素不会被添加 for (int num : nums) { uniqueSet.add(num); } // 将Set中的元素复制回数组 // 注意：HashSet不保证顺序，所以结果可能不是有序的 int index = 0; Iterator<Integer> iterator = uniqueSet.iterator(); while (iterator.hasNext()) { nums[index++] = iterator.next(); } // 返回唯一元素的数量 return uniqueSet.size(); } }算法分析
时间复杂度
添加元素到HashSet：O(n)
遍历HashSet：O(k)，其中k是唯一元素的数量
总时间复杂度：O(n)
空间复杂度
HashSet需要存储所有唯一元素：O(k) ≈ O(n)（最坏情况）
优点
代码简洁：逻辑直观，易于理解
通用性强：适用于无序数组的去重
自动去重：利用Java集合框架的特性
缺点
破坏顺序：HashSet不保证元素的插入顺序，对于有序数组会打乱原始顺序
额外空间：需要O(n)的额外空间，不符合题目原地修改的要求
性能开销：哈希表操作有一定的开销，包括哈希计算、处理哈希冲突等
适用场景
当数组无序且需要去重时
当不关心元素顺序时
当内存空间充足，可以接受O(n)额外空间时
方法二：双指针法（推荐）
双指针法是一种经典的原地算法技巧。我们使用两个指针：
快指针：遍历整个数组，寻找新的不重复元素
慢指针：指向下一个不重复元素应该存放的位置
由于数组是有序的，重复元素必然相邻，我们可以利用这个特性高效去重。
代码实现
public class TwoPointerSolution { public int removeDuplicates(int[] nums) { // 边界条件检查 if (nums == null || nums.length == 0) { return 0; } // 慢指针，指向下一个不重复元素应该存放的位置 // 初始为1，因为第一个元素肯定不需要检查 int slow = 1; // 快指针，遍历整个数组 for (int fast = 1; fast < nums.length; fast++) { // 如果当前元素不等于前一个元素，说明找到了新的不重复元素 if (nums[fast] != nums[fast - 1]) { // 将不重复元素复制到慢指针的位置 nums[slow] = nums[fast]; // 慢指针前进 slow++; } // 快指针始终前进 } // 慢指针的值就是新数组的长度 return slow; } // 更简洁的写法 public int removeDuplicatesConcise(int[] nums) { if (nums.length == 0) return 0; int i = 0; for (int j = 1; j < nums.length; j++) { if (nums[j] != nums[i]) { i++; nums[i] = nums[j]; } } return i + 1; } }算法分析
时间复杂度
只需要遍历数组一次：O(n)
空间复杂度
只使用了几个指针变量：O(1)
优点
原地修改：不需要额外空间，符合题目要求
保持顺序：保持原始数组的有序性
性能高效：只需要一次遍历，没有哈希计算开销
内存友好：适合处理大规模数据
缺点
仅适用于有序数组：对于无序数组无效
需要手动实现：相比HashSet，代码需要自己控制指针
工作原理详解
让我们通过一个例子来理解双指针法：
初始数组：[1, 1, 2, 2, 3, 4, 4, 5]
步骤：
初始化：
slow = 1,fast = 1fast=1: nums[1]=1, nums[0]=1，相等，跳过fast=2: nums[2]=2, nums[1]=1，不相等，复制到slow=1，slow=2fast=3: nums[3]=2, nums[2]=2，相等，跳过fast=4: nums[4]=3, nums[3]=2，不相等，复制到slow=2，slow=3以此类推...
最终结果：前5个元素为[1, 2, 3, 4, 5]，返回5
对比分析
| 特性 | HashSet法 | 双指针法 |
|---|---|---|
| 时间复杂度 | O(n) | O(n) |
| 空间复杂度 | O(n) | O(1) |
| 是否保持顺序 | 否 | 是 |
| 是否原地修改 | 否 | 是 |
| 适用数组类型 | 任意数组 | 有序数组 |
| 代码复杂度 | 简单 | 中等 |
| 内存使用 | 高 | 低 |
| 性能表现 | 良好（哈希计算开销） | 优秀 |
实际应用场景
适合使用HashSet的场景
处理日志去重：日志数据通常无序，且不关心顺序
用户ID去重：用户ID列表需要快速去重，且顺序不重要
数据预处理：在数据清洗阶段，需要快速识别和去重
适合使用双指针的场景
数据库查询结果去重：数据库查询结果通常有序
时间序列数据处理：时间序列数据天然有序
算法竞赛：对内存和性能有严格要求
嵌入式系统：内存受限的环境
变种问题与扩展
问题变种：保留最多k个重复元素
java
public int removeDuplicatesK(int[] nums, int k) { if (nums.length <= k) return nums.length; int slow = k; // 前k个元素肯定保留 for (int fast = k; fast < nums.length; fast++) { // 检查当前元素是否与slow-k位置的元素不同 if (nums[fast] != nums[slow - k]) { nums[slow] = nums[fast]; slow++; } } return slow; }问题变种：无序数组去重（要求原地）
java
public int removeDuplicatesUnordered(int[] nums) { // 先排序，再使用双指针法 Arrays.sort(nums); return removeDuplicates(nums); }最佳实践建议
分析问题特性：首先判断数组是否有序
考虑内存限制：如果内存受限，优先考虑双指针法
考虑顺序要求：如果需要保持顺序，选择双指针法
代码可读性：在团队开发中，选择易于理解和维护的方法
性能需求：对于性能敏感的场景，进行基准测试
总结
在有序数组去重的问题中，双指针法无疑是更优的选择。它不仅满足题目要求的原地修改和O(1)空间复杂度，而且保持数组有序，性能优异。虽然HashSet法代码更简洁，但其破坏顺序和额外空间开销的缺点使其不适用于此问题。
关键启示：
没有绝对"最好"的算法，只有最适合特定场景的算法
理解问题约束是选择算法的关键
在面试中，不仅要写出解决方案，还要能解释为什么选择这种方法
掌握这两种方法，不仅能够解决有序数组去重问题，还能为处理更复杂的数组操作问题打下坚实基础。在实际开发中，根据具体需求选择合适的算法，是每个开发者必备的技能。
