[数据结构与算法]LeetCode刷题_27_移除元素

题目
给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。
不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并原地修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

示例 1:

给定 nums = [3,2,2,3], val = 3, 函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。 你不需要考虑数组中超出新长度后面的元素。

示例 2:

给定 nums = [0,1,2,2,3,0,4,2], val = 2, 函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。

你不需要考虑数组中超出新长度后面的元素。

思路1：暴力求解法

• 暴力解法就是两层for循环，一个for循环遍历数组元素 ，第二个for循环更新数组。
• 第一个for循环遍历数组元素，第二个for循环将后边的元素前移覆盖掉需要移除的元素。

public class _27yichuyuansu {
    public static void main(String[] args) {
        int[] arr = {-1,0,3,5,9,12};
        int a = 9;
        _27yichuyuansu EZF = new _27yichuyuansu(); //创建类的对象
        int result = EZF.remove(arr,a); //调用类的函数
        System.out.println(result);
    }
    public int remove(int[] arr, int val){
        int size = arr.length;
        for (int i = 0; i < size; i++){
            if(arr[i] == val){
                for (int j = i + 1;j<size;j++){
                    arr[j-1] = arr[j];
                }
                i--;
                size--;
            }
        }
        return size;
    }
}

思路2：双指针求解法

双指针法（快慢指针法）： 通过一个快指针和慢指针在一个for循环下完成两个for循环的工作。

定义快慢指针

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

快指针和慢指针首先同时指向数组元素的第一个位置，判断如果不是要删除的元素则快指针慢指针后移，如果是需要移除的元素，快指针加一，慢指针不变。

public class _27yichuyuansu_shuangzz {
    public static void main(String[] args) {
        int[] arr = {-1,0,3,5,9,12};
        int a = 9;
        _27yichuyuansu_shuangzz EZF = new _27yichuyuansu_shuangzz(); //创建类的对象
        int result = EZF.szz_remove(arr,a); //调用类的函数
        System.out.println(result);
    }
    public int szz_remove(int[] arr,int val){
        int Slow  = 0;
        for (int fast = 0;fast <arr.length;fast++){
            if(arr[fast]!=val){
                arr[Slow] = arr[fast];
                Slow++;
            }
        }
        return Slow;
    }
}