LeetCode 27题Remove Element Rust解法bug排查求助

问题背景 #

提交的Rust解法通过了105/111个测试用例，需排查剩余测试用例的Bug。

题目要求 #

移除数组中所有等于指定值val的元素，原地修改输入数组，返回移除后数组的新长度，且新长度前的元素需包含所有不等于val的元素（顺序可任意）。

我的代码 #

pub fn remove_element(nums: &mut Vec<i32>, val: i32) -> i32 {
    let mut temp = Vec::new();
    let len = nums.len();
    for (i, v) in nums.iter().enumerate() {
        if *v == val {
            temp.push(i)
        }
    }
    let new_len = temp.len();
    temp.iter()
        .skip_while(|x| (len - new_len..len).contains(x))
        .zip((len - new_len..len).skip_while(|x| temp.contains(x)))
        .map(|(a, b)| {
            nums[*a] = nums[b];
        })
        .collect::<()>();
    (len - new_len) as i32
}

思路说明 #

• 创建temp向量存储所有等于val的元素索引
• 将nums末尾长度为temp.len()的区域设为交换区
• 把交换区中不等于val的元素与temp中不在交换区的索引位置的元素替换

错误测试用例 #

测试输入: [4,2,0,2,2,1,4,4,1,4,3,2]
我的输出: [3,2,0,2,2,1,4,1]
期望输出: [2,2,0,2,2,1,3,1]

Bug分析 #

你的核心思路方向没问题，但实现逻辑存在三个关键错误：

1. skip_while误用：skip_while仅跳过开头连续满足条件的元素，而你需要过滤掉所有位于交换区的索引，应该用filter替代。比如temp中可能存在非连续的交换区索引，skip_while会保留后面的交换区索引，导致错误替换。
2. 交换区元素筛选错误：同样用skip_while筛选交换区中不等于val的元素（即索引不在temp中的元素），只会跳过开头连续符合条件的元素，而非所有符合条件的元素，导致部分有效元素未被用来替换前面的val位置。
3. temp.contains(x)的效率与逻辑问题：contains是O(n)操作，会降低性能；同时，这种配对方式无法保证所有前面的val位置都被有效元素填充，导致最终数组前部分仍可能存在val或元素顺序不符合预期。

修复方案 #

推荐使用双指针法，这是此类原地修改数组问题的标准高效解法：

pub fn remove_element(nums: &mut Vec<i32>, val: i32) -> i32 {
    let mut slow = 0;
    for fast in 0..nums.len() {
        if nums[fast] != val {
            nums[slow] = nums[fast];
            slow += 1;
        }
    }
    slow as i32
}

双指针法思路 #

• slow指针指向当前需要填充有效元素的位置
• fast指针遍历整个数组，遇到不等于val的元素，就将其赋值到slow位置，随后slow指针后移
• 遍历结束后，slow的值即为新数组的长度，nums[0..slow]区域包含所有不等于val的元素

该方法时间复杂度O(n)，空间复杂度O(1)，能完美通过所有测试用例。

内容的提问来源于stack exchange，提问作者TomZz