[leetcode]27.移除元素

题目

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

不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并原地修改输入数组。

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

分析

对于数组而言，我们原地移除元素的话就肯定要把被移除的元素后面的全部元素都往前挪一个位，这是最基本的操作。所以最普通的暴力解法就是删除一个，整体挪动一个位。优化一点的话就是当有几个需要删除的数连在一起时，我们找到边界后一起挪动n个位，减少整体挪动的次数。

最优的是经常被用到的双指针法，下面再解释。

代码

混合暴力法

public int removeElement(int[] nums, int val) {
    int len = nums.length;
    for (int left = 0; left < len; left++) {
        if (nums[left] == val) {
            // left位于最后一个元素时
            if (left == len - 1) {
                return len - 1;
            }
            int right = left + 1;
            while (right <= len - 1 && nums[right] == val) right++;
            if (right == len - 1 && nums[right] == val) {
                // right超过长度时
                return len - (right - left);
            }
            //  把元素right处整体前移到left
            moveUp(left, right, nums, len);
            len = len - (right - left);
        }
    }
    return len;
}

// 该函数用于将right及后面的元素完前移到left位置
public void moveUp(int left, int right, int[] nums, int len) {
    int step = len - 1 - right;
    for (int i = 0; i <= step; i++) {
        nums[left + i] = nums[right + i];
    }
}

此方法其实是初步优化的暴力法，假设我们要移除值为2的元素，left指针找到第一被删除的元素，right指向left后第一个不等于2的元素，然后把从right开始的后面全部元素都往前挪至left位置。

这种方法在被删除元素都是在连续位置时可以很好提高速度。但是会有一些边界条件需要考虑，在上面代码中用注释强调了。

双指针法

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];
      }
  }
  return slowIndex;
}