LeetCode 27 - 移除元素（Remove Element）

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

问题描述

给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素。元素的顺序可能发生改变。然后返回 nums 中与 val 不同的元素的数量。

假设 nums 中不等于 val 的元素数量为 k，要通过此题，您需要执行以下操作：

  1. 更改 nums 数组，使 nums 的前 k 个元素包含不等于 val 的元素
  2. nums 的其余元素和 nums 的大小并不重要
  3. 返回 k

示例

示例 1：

1
2
3
输入：nums = [3,2,2,3], val = 3
输出：2, nums = [2,2,_,_]
解释：你的函数应该返回 k = 2, 并且 nums 中的前两个元素均为 2。

示例 2：

1
2
3
4
输入：nums = [0,1,2,2,3,0,4,2], val = 2
输出：5, nums = [0,1,4,0,3,_,_,_]
解释：你的函数应该返回 k = 5，并且 nums 中的前五个元素为 0,0,1,3,4。
注意这五个元素可以任意顺序返回。

约束条件

  • 0 <= nums.length <= 100
  • 0 <= nums[i] <= 50
  • 0 <= val <= 100

解题思路

这道题的核心是使用 双指针技巧 来原地修改数组。关键思想是：

核心思路：使用两个指针，一个慢指针 slowindex 指向下一个有效元素应该放置的位置，一个快指针 fastindex 遍历整个数组。

双指针详细解析

指针作用

  • 快指针 fastindex：负责遍历整个数组，寻找需要保留的元素
  • 慢指针 slowindex：负责记录下一个有效元素应该放置的位置

核心逻辑

  1. 快指针遍历：fastindex 从 0 开始，逐个检查数组中的每个元素
  2. 条件筛选：只有当 nums[fastindex] != val 时，才说明这是一个需要保留的元素
  3. 元素复制：将有效元素复制到慢指针位置：nums[slowindex] = nums[fastindex]
  4. 指针移动：复制完成后，慢指针自动向前移动：slowindex++
  5. 跳过无效元素：当 nums[fastindex] == val 时，快指针继续前进，慢指针不动

关键优势

  • 一次遍历：只需要遍历一次数组，时间复杂度 O(n)
  • 原地修改：不需要额外空间，直接在原数组上操作
  • 逻辑清晰：快指针负责”找”，慢指针负责”放”

算法步骤

  1. 初始化：设置 slowindex = 0，fastindex = 0
  2. 遍历数组：使用 fastindex 指针遍历整个数组
  3. 条件判断：
    • 如果 nums[fastindex] != val，说明这是一个需要保留的元素
    • 将 nums[fastindex] 复制到 nums[slowindex] 位置
    • 然后 slowindex 指针向前移动一位
  4. 返回结果：slowindex 的值就是移除指定元素后数组的长度

详细示例演练

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

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
初始状态：
nums = [3, 2, 2, 3]
slowindex = 0, fastindex = 0

步骤1: fastindex = 0
nums[0] = 3 == val (需要移除)
跳过，不执行复制操作
slowindex = 0, fastindex = 1

步骤2: fastindex = 1  
nums[1] = 2 != val (需要保留)
nums[slowindex] = nums[fastindex] → nums[0] = 2
slowindex++ → slowindex = 1, fastindex = 2

步骤3: fastindex = 2
nums[2] = 2 != val (需要保留)  
nums[slowindex] = nums[fastindex] → nums[1] = 2
slowindex++ → slowindex = 2, fastindex = 3

步骤4: fastindex = 3
nums[3] = 3 == val (需要移除)
跳过，不执行复制操作
slowindex = 2, fastindex = 4 (结束)

最终结果：
nums = [2, 2, 3, 3]  (前2个元素是有效元素)
返回 slowindex = 2

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

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
初始状态：
nums = [0, 1, 2, 2, 3, 0, 4, 2]
slowindex = 0, fastindex = 0

步骤1: fastindex = 0
nums[0] = 0 != val (需要保留)
nums[0] = 0, slowindex = 1, fastindex = 1

步骤2: fastindex = 1
nums[1] = 1 != val (需要保留)
nums[1] = 1, slowindex = 2, fastindex = 2

步骤3: fastindex = 2
nums[2] = 2 == val (需要移除)
跳过，slowindex = 2, fastindex = 3

步骤4: fastindex = 3
nums[3] = 2 == val (需要移除)
跳过，slowindex = 2, fastindex = 4

步骤5: fastindex = 4
nums[4] = 3 != val (需要保留)
nums[2] = 3, slowindex = 3, fastindex = 5

步骤6: fastindex = 5
nums[5] = 0 != val (需要保留)
nums[3] = 0, slowindex = 4, fastindex = 6

步骤7: fastindex = 6
nums[6] = 4 != val (需要保留)
nums[4] = 4, slowindex = 5, fastindex = 7

步骤8: fastindex = 7
nums[7] = 2 == val (需要移除)
跳过，slowindex = 5, fastindex = 8 (结束)

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

实现细节

关键点分析

  1. 原地修改：不需要额外的数组空间，直接在原数组上操作
  2. 双指针移动：慢指针只在找到有效元素时才移动
  3. 元素覆盖：有效元素会覆盖掉需要移除的元素位置

边界情况处理

  • 空数组：nums.length = 0，直接返回 0
  • 所有元素都等于 val：slow 始终为 0，返回 0
  • 没有元素等于 val：所有元素都被保留，slow 等于原数组长度

代码实现

Java 实现（双指针方法）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int removeElement(int[] nums, int val) {
        int slowindex = 0;  // 慢指针，指向下一个有效元素应该放置的位置
        
        // 快指针遍历整个数组
        for(int fastindex = 0; fastindex < nums.length; fastindex++) {
            // 如果当前元素不等于要移除的值，则保留
            if(nums[fastindex] != val) {
                nums[slowindex++] = nums[fastindex];  // 将有效元素放到慢指针位置，然后慢指针前移
            }
            // 如果 nums[fastindex] == val，则跳过，慢指针不动
        }
        
        return slowindex;  // 返回有效元素的个数
    }
}

代码逐行解析

1
int slowindex = 0;  // 初始化慢指针，指向数组的第一个位置
1
2
for(int fastindex = 0; fastindex < nums.length; fastindex++) {
    // 快指针从0开始，遍历到数组末尾
1
2
if(nums[fastindex] != val) {
    // 检查当前元素是否需要保留
1
2
3
4
5
nums[slowindex++] = nums[fastindex];
// 这行代码等价于：
// nums[slowindex] = nums[fastindex];
// slowindex++;
// 将有效元素复制到慢指针位置，然后慢指针向前移动
1
return slowindex;  // 慢指针的值就是有效元素的个数

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

暴力解法（你的第一个代码）

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

暴力解法的问题：

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

双指针解法（优化后）

1
2
3
4
5
6
7
8
9
10
public int removeElement(int[] nums, int val) {
    int slowindex = 0;
    
    for(int fastindex = 0; fastindex < nums.length; fastindex++) {
        if(nums[fastindex] != val) {
            nums[slowindex++] = nums[fastindex]; 
        }
    }
    return slowindex;
}

双指针解法的优势：

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

方法比较

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

复杂度分析

时间复杂度

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

空间复杂度

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

双指针技巧深入理解

为什么叫”双指针”？

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

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

双指针的核心思想

  1. 分工明确：

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

  2. 同步移动：

    • 快指针总是向前移动
    • 慢指针只在找到有效元素时才移动

  3. 空间复用：

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

双指针的适用场景

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

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

常见双指针模式

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

1
2
3
4
5
6
int slow = 0;
for(int fast = 0; 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
24
public int removeElement(int[] nums, int val) {
    int slowindex = 0;
    
    System.out.println("初始数组: " + Arrays.toString(nums));
    System.out.println("要移除的值: " + val);
    
    for(int fastindex = 0; fastindex < nums.length; fastindex++) {
        System.out.printf("步骤 %d: fastindex=%d, slowindex=%d, nums[%d]=%d", 
                         fastindex + 1, fastindex, slowindex, fastindex, nums[fastindex]);
        
        if(nums[fastindex] != val) {
            nums[slowindex] = nums[fastindex];
            slowindex++;
            System.out.printf(" -> 保留，复制到位置%d\n", slowindex - 1);
        } else {
            System.out.println(" -> 跳过");
        }
        
        System.out.println("当前数组: " + Arrays.toString(nums));
    }
    
    System.out.println("最终结果: " + slowindex + " 个有效元素");
    return slowindex;
}

关键收获

重要概念

  1. 双指针技巧：在处理数组问题时，双指针是常用的优化技巧
  2. 原地修改：在不使用额外空间的情况下修改数组
  3. 快慢指针：慢指针记录有效位置，快指针遍历数组
  4. 空间复用：利用数组前面的空间存储有效元素

常见陷阱

  1. 忘记移动慢指针：只有在找到有效元素时才移动慢指针
  2. 边界条件：注意处理空数组和所有元素都需要移除的情况
  3. 理解题意：题目不要求保持原有顺序，只需要前 k 个元素有效
  4. 索引混淆：注意区分快指针和慢指针的作用

解题思路总结

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

相关问题

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