移除元素

leecode 27 26  283 844 977

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

示例 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。

一、暴力解法

利用循环比较每当当前索引的值等于目标val的值的时候，将它后一个数的值赋给当前，并将索引和长度-1；

class Solution {
  public int removeElement(int[] nums, int val) {
        int length = nums.length();
        for (int i = 0; i < length; i++) {
            if (nums[i] == val) { // 发现需要移除的元素，就将数组集体向前移动一位
                for (int j = i + 1; j < length; j++) {
                    nums[j - 1] = nums[j];
                }
                i--; // 因为下标i以后的数值都向前移动了一位，所以i也向前移动一位
                length--; // 此时数组的大小-1
            }
        }
        return length;

    }
}

 二、双指针法

定义快慢指针。用一个for循环控制两个指针。如果快指针不等于目标值，快慢指针同时前进，如果快指针等于目标值，则慢指针保持不了。返回慢指针的索引即是长度。

class Solution {
    public int removeElement(int[] nums, int val) {

        // 快慢指针
        int fastIndex = 0;
        int slowIndex;
        for (slowIndex = 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 (left <= right) {
            if (nums[left] == val) {
                nums[left] = nums[right];
                right--;
            } else {
                left++;
            }
        }
        return left;
    }
}