27. 移除元素

题目描述

给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。

不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

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

解题思路

线性算法，找到一个要移除的元素就和最后一个交换

#![allow(unused)]
fn main() {
struct Solution {}

impl Solution {
    pub fn remove_element(nums: &mut Vec<i32>, val: i32) -> i32 {
        let n = nums.len();
        if n == 0 { return 0 }
        // [i,j) 表示还需要处理的区间，在这个区间之外的都是无需处理的
        let mut i = 0;
        let mut j = n;
        while i < j {
            if nums[i] == val {
                j -= 1;
                nums[i] = nums[j];
            } else {
                i += 1;
            }
        }
        j as i32
    }
}
}

学习感想

一开始想的时候其实有不变量的思想在里面

写一下 双指针的版本

#![allow(unused)]
fn main() {
struct Solution {}
impl Solution {
    pub fn remove_element(nums: &mut Vec<i32>, val: i32) -> i32 {
        let mut a = 0;
        let mut b = 0;
        let n = nums.len();
        while b < n {
            if nums[b] == val { b += 1 }
            else {
                nums[a] = nums[b];
                a += 1;
                b += 1;
            }
        }
        a as i32
    }
}
}

std强大的标准库 Vec上retain方法

#![allow(unused)]
fn main() {
struct Solution {}
impl Solution {
    pub fn remove_element(nums: &mut Vec<i32>, val: i32) -> i32 {
        nums.retain(|&x| x != val);
        nums.len() as i32
    }
}

}

slow指针用来存储需要留下元素应该存放的地址，fast指针是当前处理的元素

#![allow(unused)]
fn main() {
struct Solution {}
impl Solution {
    pub fn remove_element(nums: &mut Vec<i32>, val: i32) -> i32 {
        let mut slow: usize = 0usize;    // the result elem
        let mut fast: usize = 0usize;    // the processing elem
        while fast < nums.len() {
            if nums[fast] == val { fast += 1usize }
            else {
                nums[slow] = nums[fast]; // move elem
                slow += 1usize;
                fast += 1usize;
            }
        }
        slow as i32
    }
}
}