移除元素

学习文本来源:代码随想录

力扣地址

给你一个数组nums和一个值val,你需要原地移除所有数值等于val的元素,并返回移除后的数组的新长度。
不要使用额外耳朵数组空间,你必须仅使用O(1)额外空间并原地修改数组。
元素的顺序可以改变,你不需要考虑数组中超出长度后面的元素。
示例1:给定nums=[3,2,2,3], val=3,函数应该返回新的长度2,并且nums中的前两个元素均为2。你不需要考虑数组中超出长度后面的元素。
示例2:给定nums=[0,1,2,2,3,9,4,2],val=2,函数应该返回新的长度5,并且nums中千五个元素为0,1,3,0,4
你不需要考虑数组中超出新长度后面的元素

思路

有的同学可能说了,多余的元素,删掉不就得了。
要知道,数组元素的内存地址是连续的,不能单独删除数组中的某个元素,只能覆盖。

暴力解法

这个题目暴力的解法就是两层for循环,一个for便利数组元素,第二for循环更新数组。

很明显暴力解法的时间复杂度是O(n^2),这道题目暴力解法在力扣上是能过的。

双指针法

双指针法(快慢指针法):通过一个快指针和慢指针在一个for循环下完成两个for循环的工作。
定义快慢指针

  • 快指针:寻找新数组元素,新数组元素就是不含有目标元素的数组
  • 慢指针:指向更新新数组下标的位置

很多同学这道题目做的很懵,就是不理解快慢指针究竟都是什么含义,所以一定要明确含义,后面的思路就容易理解了。

双指针法(快慢指针法)在数组和链表的操作中是非常常见的,很多考察数组、链表、字符串等操作的面试题,都使用双指针法。

java:

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];
                slowIndex++;
            }
        }
        return slowIndex;
    }
}

//相向双指针法
class Solution {
    public int removeElement(int[] nums, int val) {
        int left = 0;
        int right = nums.length - 1;
        while(right >= 0 && nums[right] == val) right--; //将right移到从右数第一个值不为val的位置
        while(left <= right) {
            if(nums[left] == val) { //left位置的元素需要移除
                //将right位置的元素移到left(覆盖),right位置移除
                nums[left] = nums[right];
                right--;
            }
            left++;
            while(right >= 0 && nums[right] == val) right--;
        }
        return left;
    }
}

// 相向双指针法(版本二)
class Solution {
    public int removeElement(int[] nums, int val) {
        int left = 0;
        int right = nums.length - 1;
        while(left <= right){
            if(nums[left] == val){
                nums[left] = nums[right];
                right--;
            }else {
                // 这里兼容了right指针指向的值与val相等的情况
                left++;
            }
        }
        return left;
    }
}

golang:

func removeElement(nums []int, val int) int {
    slow := 0
    for fast,v := range nums {
        if v != val{
            nums[slow] = nums[fast]
            slow++
        }
    }
    nums = nums[:slow]
    return slow
}


//相向双指针法
func removeElement(nums []int, val int) int {
    left := 0
    right := len(nums)-1
    for left<=right {
        if nums[left] == val {
            nums[left] = nums[right]
            right--
        }else{
            left++
        }
    }
}
Last modification:May 28, 2024
如果觉得我的文章对你有用,请收藏本站