AI毛毛的blog

leetcode打卡-0027移除元素

题目描述

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

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

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/remove-element

解题思路

1. 双指针

这题和leetcode第26题几乎一样的思路，已经在这里记录过题解。

用一个慢指针slow指向有效数组的最后一个位置，用来记录符合条件的数组尾部，用一个快指针fast顺序遍历数组。

当fast指针所指的值与val不一致时，将slow后一位的值改为fast指向的值，slow前进一位，fast继续遍历即可。

1
2
3
4
5
6
7
8
9
10
11
# Python实现

class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        # 双指针法：同删除相同元素方法一样
        j = 0
        for i in range(len(nums)):
            if nums[i] != val:
                nums[j] = nums[i]
                j += 1
        return j

顺便练习一下Rust

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
impl Solution {
    pub fn remove_element(nums: &mut Vec<i32>, val: i32) -> i32 {
        if nums.is_empty() {
            return 0;
        }

        let mut i = 0;
        for j in 0..nums.len() {
            if nums[j] != val {
                nums[i] = nums[j];
                i += 1;
            }
        }
        i as i32
    }
}

总结

对于这种字符串、数组之类的可以直接遍历的题目，利用具体要求提炼出“保留逻辑”，将这种逻辑应用到遍历中的每一个位置即可。