27 移除元素.md

27、移除元素

题目：

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

不要使用额外的空间，你必须在原地修改并使用O(1)的额外空间下完成。

元素的顺序可以改变。

给定 nums = [0,1,2,2,3,0,4,2], val = 2,

函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。

注意这五个元素可为任意顺序。

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

一定要看清题目，是移除指定元素，而不是移除重复元素。

解法一（双指针赋值法）：

• 设置快慢两个指针
• 快指针先走遍历
• 方法A：当快指针的值不等于k的时候，把快指针的值赋给慢指针的值，等于k的话，快指针跳过。这样的话，
  • 如果不存在指定元素k，快指针和慢指针相同，只是原地赋值
  • 如果存在，慢指针比快指针慢，记录移除k后的数组
• 方法B：当然也可以让快指针等于k的 时候，continue

public int removeElement(int[] nums, int k){
    int i=0;
    for(int j=0; j<nums.length; j++){
        if(nums[j] != k){
            nums[i] = nums[j];
            i++;
        }
    }
    
    //当快指针把最后一个值赋给慢指针的时候，仍然执行了i++，所以代码结束后i等于最终数组的长度
    return i;
}

时间复杂度当然是O(n）,空间复杂度O(1)

解法二（双指针交换法）：

这真是一种巧妙的方法，遇到k就和最后的元素交换。

public int removeElement(int[] nums, int k){
    int i = 0;
    int n = nums.length;
    
    while(i<n){
        if(nums[i] == k){
            nums[i] = nums[--n];
        }else{
            i++;
        }
    }
    
    //最后一个n总会和最后的数组相邻，所以n比最后数组的下标大1，故返回n
    return n;
}