LeetCode 26 - 删除有序数组中的重复项（Remove Duplicates from Sorted Array）

算法刷题>LeetCode>面试经典150
6k words

问题描述

给你一个 非严格递增排列 的数组 nums，请你 原地 删除重复出现的元素，使每个元素 只出现一次，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致。然后返回 nums 中唯一元素的个数。

考虑 nums 的唯一元素的数量为 k，你需要做以下事情确保你的题解可以被通过：

  1. 更改数组 nums，使 nums 的前 k 个元素包含唯一元素，并按照它们最初在 nums 中出现的顺序排列。nums 的其余元素与 nums 的大小不重要。
  2. 返回 k。

示例

示例 1：

1
2
3
输入：nums = [1,1,2]
输出：2, nums = [1,2,_]
解释：函数应该返回新的长度 2，并且原数组 nums 的前两个元素被修改为 1, 2。不需要考虑数组中超出新长度后面的元素。

示例 2：

1
2
3
输入：nums = [0,0,1,1,1,2,2,3,3,4]
输出：5, nums = [0,1,2,3,4,_,_,_,_,_]
解释：函数应该返回新的长度 5，并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4。不需要考虑数组中超出新长度后面的元素。

约束条件

  • 1 <= nums.length <= 3 * 10^4
  • -100 <= nums[i] <= 100
  • nums 已按 非严格递增 排列

解题思路

这道题的核心是使用 双指针技巧 来原地删除重复元素。由于数组已经排序，重复元素必然相邻，这大大简化了问题。

核心思路：使用两个指针，一个慢指针 slow 指向下一个唯一元素应该放置的位置，一个快指针 fast 遍历整个数组寻找新的唯一元素。

双指针详细解析

指针作用

  • 快指针 fast：负责遍历整个数组，寻找与当前唯一元素不同的新元素
  • 慢指针 slow：负责记录下一个唯一元素应该放置的位置

核心逻辑

  1. 快指针遍历：fast 从 1 开始（因为第一个元素肯定是唯一的）
  2. 比较元素：比较 nums[fast] 和 nums[slow-1]（当前最后一个唯一元素）
  3. 发现新元素：当 nums[fast] != nums[slow-1] 时，说明找到了新的唯一元素
  4. 元素复制：将新元素复制到慢指针位置：nums[slow] = nums[fast]
  5. 指针移动：复制完成后，慢指针向前移动：slow++

关键优势

  • 一次遍历：只需要遍历一次数组，时间复杂度 O(n)
  • 原地修改：不需要额外空间，直接在原数组上操作
  • 保持顺序：由于数组已排序，自然保持了相对顺序

算法步骤

  1. 初始化：设置 slow = 1（第一个元素肯定是唯一的）
  2. 遍历数组：使用 fast 指针从索引 1 开始遍历整个数组
  3. 条件判断：
    • 如果 nums[fast] != nums[slow-1]，说明找到了新的唯一元素
    • 将 nums[fast] 复制到 nums[slow] 位置
    • 然后 slow 指针向前移动一位
  4. 返回结果：slow 的值就是去重后数组的长度

详细示例演练

示例1：nums = [1,1,2]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
初始状态：
nums = [1, 1, 2]
slow = 1, fast = 1

步骤1: fast = 1
nums[1] = 1, nums[slow-1] = nums[0] = 1
nums[1] == nums[0] (重复元素)
跳过，不执行复制操作
slow = 1, fast = 2

步骤2: fast = 2
nums[2] = 2, nums[slow-1] = nums[0] = 1
nums[2] != nums[0] (新元素)
nums[slow] = nums[fast] → nums[1] = 2
slow++ → slow = 2, fast = 3 (结束)

最终结果：
nums = [1, 2, 2]  (前2个元素是唯一元素)
返回 slow = 2

示例2：nums = [0,0,1,1,1,2,2,3,3,4]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
初始状态：
nums = [0, 0, 1, 1, 1, 2, 2, 3, 3, 4]
slow = 1, fast = 1

步骤1: fast = 1
nums[1] = 0, nums[0] = 0
nums[1] == nums[0] (重复)
跳过，slow = 1, fast = 2

步骤2: fast = 2
nums[2] = 1, nums[0] = 0
nums[2] != nums[0] (新元素)
nums[1] = 1, slow = 2, fast = 3

步骤3: fast = 3
nums[3] = 1, nums[1] = 1
nums[3] == nums[1] (重复)
跳过，slow = 2, fast = 4

步骤4: fast = 4
nums[4] = 1, nums[1] = 1
nums[4] == nums[1] (重复)
跳过，slow = 2, fast = 5

步骤5: fast = 5
nums[5] = 2, nums[1] = 1
nums[5] != nums[1] (新元素)
nums[2] = 2, slow = 3, fast = 6

步骤6: fast = 6
nums[6] = 2, nums[2] = 2
nums[6] == nums[2] (重复)
跳过，slow = 3, fast = 7

步骤7: fast = 7
nums[7] = 3, nums[2] = 2
nums[7] != nums[2] (新元素)
nums[3] = 3, slow = 4, fast = 8

步骤8: fast = 8
nums[8] = 3, nums[3] = 3
nums[8] == nums[3] (重复)
跳过，slow = 4, fast = 9

步骤9: fast = 9
nums[9] = 4, nums[3] = 3
nums[9] != nums[3] (新元素)
nums[4] = 4, slow = 5, fast = 10 (结束)

最终结果：
nums = [0, 1, 2, 3, 4, 1, 2, 3, 3, 4]  (前5个元素是唯一元素)
返回 slow = 5

实现细节

关键点分析

  1. 有序数组优势：由于数组已排序，重复元素必然相邻，简化了比较逻辑
  2. 双指针移动：慢指针只在找到新唯一元素时才移动
  3. 元素覆盖：新唯一元素会覆盖掉重复元素的位置

边界情况处理

  • 单元素数组：nums.length = 1，直接返回 1
  • 无重复元素：所有元素都不同，slow 等于原数组长度
  • 全部重复：所有元素都相同，slow 始终为 1

代码实现

Java 实现（双指针方法）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int removeDuplicates(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
        
        int slow = 1;  // 慢指针，指向下一个唯一元素应该放置的位置
        
        // 快指针从索引1开始遍历整个数组
        for (int fast = 1; fast < nums.length; fast++) {
            // 如果当前元素与上一个唯一元素不同，则保留
            if (nums[fast] != nums[slow - 1]) {
                nums[slow] = nums[fast];  // 将新唯一元素放到慢指针位置
                slow++;  // 慢指针前移
            }
            // 如果 nums[fast] == nums[slow-1]，则跳过，慢指针不动
        }
        
        return slow;  // 返回唯一元素的个数
    }
}

代码逐行解析

1
2
3
4
if (nums.length == 0) {
    return 0;
}
// 处理空数组的边界情况
1
int slow = 1;  // 初始化慢指针，第一个元素肯定是唯一的
1
2
3
for (int fast = 1; fast < nums.length; fast++) {
    // 快指针从索引1开始，遍历到数组末尾
}
1
2
3
if (nums[fast] != nums[slow - 1]) {
    // 检查当前元素是否与上一个唯一元素不同
}
1
2
nums[slow] = nums[fast];  // 将新唯一元素复制到慢指针位置
slow++;  // 慢指针向前移动
1
return slow;  // 慢指针的值就是唯一元素的个数

简化版本（更简洁的写法）

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int removeDuplicates(int[] nums) {
        int slow = 1;
        
        for (int fast = 1; fast < nums.length; fast++) {
            if (nums[fast] != nums[slow - 1]) {
                nums[slow++] = nums[fast];  // 合并赋值和递增操作
            }
        }
        
        return slow;
    }
}

对比：暴力解法 vs 双指针解法

暴力解法（不推荐）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int removeDuplicates(int[] nums) {
    int length = nums.length;
    
    for (int i = 1; i < length; i++) {
        if (nums[i] == nums[i - 1]) {
            // 发现重复元素，将后面的所有元素向前移动一位
            for (int j = i; j < length - 1; j++) {
                nums[j] = nums[j + 1];
            }
            length--;  // 数组长度减1
            i--;  // 因为元素前移，需要重新检查当前位置
        }
    }
    return length;
}

暴力解法的问题：

  • 时间复杂度：O(n²) - 每次删除重复元素都需要移动后面的所有元素
  • 效率低下：对于每个重复元素，都要执行 O(n) 的移动操作
  • 代码复杂：需要处理数组长度变化和索引回退

双指针解法（推荐）

1
2
3
4
5
6
7
8
9
10
public int removeDuplicates(int[] nums) {
    int slow = 1;
    
    for (int fast = 1; fast < nums.length; fast++) {
        if (nums[fast] != nums[slow - 1]) {
            nums[slow++] = nums[fast]; 
        }
    }
    return slow;
}

双指针解法的优势：

  • 时间复杂度：O(n) - 只需要一次遍历
  • 空间复杂度：O(1) - 只使用常数额外空间
  • 代码简洁：逻辑清晰，易于理解和维护

方法比较

方面 双指针方法 暴力方法
时间复杂度 O(n) O(n²)
空间复杂度 O(1) O(1)
遍历次数 1次 最多n次（每个重复元素都要移动）
代码复杂度 简单 复杂
执行效率 高效 低效
优点 一次遍历，逻辑清晰 思路直观
缺点 需要理解双指针概念 效率低，代码复杂
推荐度 ★★★★★ ★★☆☆☆

复杂度分析

时间复杂度

  • O(n)：只需要遍历一次数组，其中 n 是数组的长度
  • 每个元素最多被访问一次，没有嵌套循环

空间复杂度

  • O(1)：只使用了常数额外空间（两个指针变量）
  • 没有使用额外的数组或其他数据结构

双指针技巧深入理解

为什么叫”双指针”？

虽然这里使用的是两个整数变量 slow 和 fast，但它们本质上是指向数组位置的”指针”：

  • 指针：指向数组中某个位置的索引
  • 双指针：使用两个索引来协同工作，解决数组问题

双指针的核心思想

  1. 分工明确：

    • 快指针：负责”探索”，遍历整个数组
    • 慢指针：负责”收集”，记录唯一元素的位置

  2. 同步移动：

    • 快指针总是向前移动
    • 慢指针只在找到新唯一元素时才移动

  3. 空间复用：

    • 利用数组前面的空间存储唯一元素
    • 避免使用额外的数组空间

双指针的适用场景

双指针技巧特别适用于以下类型的数组问题：

  • 原地删除：需要删除数组中的某些元素
  • 去重：移除数组中的重复元素
  • 分区：将数组按某种条件分成两部分
  • 合并：合并两个有序数组

常见双指针模式

模式1：快慢指针（本题使用）

1
2
3
4
5
6
int slow = 1;
for (int fast = 1; fast < nums.length; fast++) {
    if (condition) {
        nums[slow++] = nums[fast];
    }
}

模式2：左右指针

1
2
3
4
5
6
int left = 0, right = nums.length - 1;
while (left < right) {
    // 根据条件移动指针
    if (condition) left++;
    else right--;
}

调试技巧

为了更好地理解双指针的工作过程，可以在代码中添加调试输出：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public int removeDuplicates(int[] nums) {
    int slow = 1;
    
    System.out.println("初始数组: " + Arrays.toString(nums));
    
    for (int fast = 1; fast < nums.length; fast++) {
        System.out.printf("步骤 %d: fast=%d, slow=%d, nums[%d]=%d, nums[%d]=%d", 
                         fast, fast, slow, fast, nums[fast], slow-1, nums[slow-1]);
        
        if (nums[fast] != nums[slow - 1]) {
            nums[slow] = nums[fast];
            slow++;
            System.out.printf(" -> 保留，复制到位置%d\n", slow - 1);
        } else {
            System.out.println(" -> 跳过");
        }
        
        System.out.println("当前数组: " + Arrays.toString(nums));
    }
    
    System.out.println("最终结果: " + slow + " 个唯一元素");
    return slow;
}

关键收获

重要概念

  1. 双指针技巧：在处理数组问题时，双指针是常用的优化技巧
  2. 原地修改：在不使用额外空间的情况下修改数组
  3. 快慢指针：慢指针记录有效位置，快指针遍历数组
  4. 有序数组优势：排序数组使重复元素相邻，简化了比较逻辑

常见陷阱

  1. 忘记移动慢指针：只有在找到新唯一元素时才移动慢指针
  2. 边界条件：注意处理空数组和单元素数组的情况
  3. 理解题意：题目要求保持相对顺序，返回唯一元素个数
  4. 索引混淆：注意区分快指针和慢指针的作用

解题思路总结

  1. 识别问题类型：需要原地删除重复元素
  2. 选择算法：双指针技巧是最优解
  3. 实现步骤：
    • 初始化两个指针
    • 快指针遍历，慢指针收集
    • 返回慢指针位置

相关问题

这道题是双指针技巧的经典应用，与 LeetCode 27 题（移除元素）非常相似。掌握了这个模式后，可以解决很多类似的数组操作问题。通过对比暴力解法和双指针解法，我们可以清楚地看到算法优化的重要性。