移除元素

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

力扣地址

给你一个数组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++
        }
    }
}