双指针法实现有序数组去重与性能优化-育师

1. 问题分析与解题思路

这道题目要求我们原地删除有序数组中的重复项，并返回新数组的长度。关键在于"原地"二字，意味着我们不能使用额外的数组空间，必须在原数组上进行操作。这在实际开发中很常见，比如处理大型数据集时，内存优化就显得尤为重要。

双指针法是解决这类问题的经典方法。想象你在整理书架上的书籍，左手(p)指向当前整理好的最后一本不重复的书，右手(q)则不断向右扫描寻找下一本不同的书。当右手找到不同的书时，就把它放到左手边的下一个位置，然后左手向右移动一位。

这种方法的优势在于：

时间复杂度O(n)：只需遍历一次数组
空间复杂度O(1)：不需要额外存储空间
原地操作：直接在原数组上修改，节省内存

2. 基础双指针实现详解

让我们深入分析基础版的双指针实现：

class Solution { public int removeDuplicates(int[] nums) { // 边界处理 if(nums.length == 0 || nums == null){ return 0; } // 双指针初始化 int p = 0; // 慢指针，指向当前唯一序列的末尾 int q = 1; // 快指针，用于遍历数组 while(q < nums.length){ if(nums[p] != nums[q]){ // 发现新元素，放到唯一序列的下一个位置 nums[p + 1] = nums[q]; // 移动慢指针 p++; } // 无论是否发现新元素，快指针都要前进 q++; } // 返回唯一序列的长度 return p + 1; } }

2.1 关键点解析

边界处理：空数组或null输入直接返回0，这是良好的编程习惯
指针初始化：
- p从0开始，因为第一个元素必定是唯一的
- q从1开始，因为需要与p位置的元素比较
核心逻辑：
- 当nums[p] != nums[q]时，说明找到了新元素
- 将新元素放到p+1位置，然后p前进
- q始终前进，遍历整个数组

注意：这里p+1的位置可能和q相同，导致"自我覆盖"。虽然不影响结果，但可以优化。

3. 优化版双指针实现

针对基础版的"自我覆盖"问题，我们可以添加一个判断条件：

class Solution { public int removeDuplicates(int[] nums) { if(nums.length == 0 || nums == null){ return 0; } int p = 0; int q = 1; while(q < nums.length){ if(nums[p] != nums[q]){ // 只有当q和p不相邻时才需要移动 if(q - p > 1){ nums[p + 1] = nums[q]; } p++; } q++; } return p + 1; } }

3.1 优化点分析

避免不必要的赋值：
- 当q == p+1时，赋值操作是多余的
- 添加q-p>1的判断可以跳过这种情况
性能影响：
- 对于完全唯一的数组，可以避免所有赋值操作
- 对于有重复的数组，仅在有间隔时才进行赋值
实际效果：
- 减少了内存写入次数
- 对时间复杂度没有影响，仍是O(n)

4. 复杂度分析与对比

4.1 时间复杂度

两种实现的时间复杂度都是O(n)，因为：

只需要遍历数组一次
每个元素最多被比较和移动一次

4.2 空间复杂度

两种实现的空间复杂度都是O(1)，因为：

只使用了固定数量的额外变量(p,q)
没有使用与输入规模相关的额外空间

4.3 实际性能差异

虽然时间复杂度相同，但优化版在实际运行中可能更快：

减少了不必要的内存写入
现代CPU对内存操作比计算更敏感
对于大型数组，这种优化可能更明显

5. 常见问题与调试技巧

5.1 边界条件测试

在实现这类算法时，务必测试以下边界情况：

空数组[]
单元素数组[1]
全相同数组[1,1,1]
全不同数组[1,2,3]
一般情况[1,1,2,3,3,4]

5.2 调试技巧

打印指针位置：在循环中添加打印语句，观察p,q的变化
```
System.out.println("p="+p+", q="+q+", nums="+Arrays.toString(nums));
```
单步调试：使用IDE的调试功能，逐步执行观察变量变化
可视化工具：在纸上画出数组和指针位置的变化

5.3 常见错误

忘记边界检查：直接开始处理数组可能导致空指针异常
指针移动错误：在发现新元素时，忘记移动p指针
返回值错误：返回p而不是p+1
数组越界：q的循环条件写错，导致数组访问越界

6. 算法扩展与变种

6.1 保留k个重复项

如果需要保留最多k个重复项，可以这样修改：

int k = 2; // 保留最多2个重复项 if(p < k || nums[p-k] != nums[q]){ nums[p] = nums[q]; p++; } q++;

6.2 无序数组去重

对于无序数组，可以先排序再使用双指针，或者使用HashSet：

Set<Integer> set = new HashSet<>(); int p = 0; for(int num : nums){ if(set.add(num)){ nums[p++] = num; } } return p;

6.3 链表去重

类似思路可以应用于有序链表去重：

ListNode current = head; while(current != null && current.next != null){ if(current.val == current.next.val){ current.next = current.next.next; } else { current = current.next; } } return head;

7. 实际应用场景

这种双指针技术在以下场景中非常有用：

数据库查询结果处理：去除重复记录
日志分析：合并相同类型的日志条目
图像处理：去除连续的相同像素
数据压缩：行程长度编码(RLE)的基础
实时数据处理：流数据中的重复检测

8. 性能优化进阶

对于特别大的数组，可以考虑：

并行处理：将数组分段，多线程处理
SIMD指令：利用CPU的向量指令加速比较
位图法：如果元素范围有限，可以使用位图标记

不过这些优化通常只在特定场景下才有明显效果，对于LeetCode这类问题，双指针已经是最优解。

9. 语言特性适配

虽然示例使用Java，但算法思想是通用的：

Python实现：

def removeDuplicates(nums): if not nums: return 0 p = 0 for q in range(1, len(nums)): if nums[p] != nums[q]: p += 1 nums[p] = nums[q] return p + 1

C++实现：

int removeDuplicates(vector<int>& nums) { if(nums.empty()) return 0; int p = 0; for(int q = 1; q < nums.size(); q++){ if(nums[p] != nums[q]){ nums[++p] = nums[q]; } } return p + 1; }