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。

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

思路

多余的元素，删除即可，但是数组的元素在内存地址中是连续的，不能单独删除数组中的某个元素，只能覆盖
**

解法一：暴力解法

package leetcode;
import java.util.Arrays;
public class leetcode_27_1 {
    public int removeElement(int[] nums, int val) {
        int size = nums.length;
        for(int i = 0; i < size; i++){
            if(nums[i] == val){
                for(int j = i + 1; j < size; j ++){
                    nums[j - 1] = nums[j];
                }
                i --;  // 因为下表i以后的数值都向前移动了一位，所以i也向前移动一位
                size --;  // 此时数组的大小-1
            }
        }
        System.out.println(Arrays.toString(nums));
        System.out.println(size);
        return size;
    }
    public static void main(String[] args){
        leetcode_27_1 lt = new leetcode_27_1();
        int[] nums = new int[]{3,2,2,3};
        int size = lt.removeElement(nums, 3);
    }
}

时间复杂度：O(n^2)

解法二：双指针法

通过一个快指针和慢指针在一个for循环下完成两个for循环的工作

当与给定的值相等时，递增以跳过该元素。只要，我们就复制到并同时递增两个索引。重复这一过程，直到到达数组的末尾，该数组的新长度为

public int removeElement(int[] nums, int val) {
    int i = 0;
    for (int j = 0; j < nums.length; j++) {
        if (nums[j] != val) {
            nums[i] = nums[j];
            i++;
        }
    }
    return i;
}

时间复杂度：O(n)
空间复杂度：O(1)

当我们遇到时，我们可以将当前元素与最后一个元素进行交换，并释放最后一个元素。这实际上使数组的大小减少了 1。被交换的最后一个元素可能是您想要移除的值。在下一次迭代中，仍然会检查这个元素

public int removeElement(int[] nums, int val) {
    int i = 0;
    int n = nums.length;
    while (i < n) {
        if (nums[i] == val) {
            nums[i] = nums[n - 1];
            // reduce array size by one
            n--;
        } else {
            i++;
        }
    }
    return n;
}

时间复杂度：O(n)
空间复杂度：O(1)