移除元素（27）

题目

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

不要使用额外的数组空间，你必须仅使用 O(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不同的项依次覆盖到数组的前n项，n即为结果

function removeElement(nums, val) {
  let n = 0
  for(let i = 0; i < nums.length; i++) {
    if (nums[i] !== val) {
      nums[n] = nums[i]
      n++
    }
  }
  return n
}

交换

交换移除：遍历nums，左指针指向第一个元素位置0，右指针指向最后一个元素位置length-1。遍历开始左指针+1，当当前值与val相同时，交换左右指针的值，此时左指针-1，右指针-1，遍历的结束位置（之后全部是val相等的值）应该也-1。所以length即为结果

function removeElement(nums, val) {
  let length = nums.length;
	let i = 0,
		j = nums.length - 1;
	for (; i < length; i++) {
		if (nums[i] === val) {
			let temp = nums[i];
			nums[i] = nums[j];
			temp = nums[j];
			i--;
			j--;
			length--;
		}
	}
	return length;
}

双指针

双指针：类似方法二，左指针指向第一个元素，右指针指向最后一个元素，若左指针遇到等于val的值，则使用右指针的值覆盖左指针，此时右指针-1；若左指针的值不等于val，那么左指针+1。结束条件是左指针大于右指针。左指针指向的第i个位置即为结果i

function removeElement(nums, val) {
  let i = 0,
		j = nums.length - 1;
	while (i <= j) {
		if (nums[i] === val) {
			nums[i] = nums[j];
			j--;
		} else {
			i++;
		}
	}
	return i;
}

splice()

遍历数组，遇到等于val的值则使用splice()删除

function removeElement(nums, val) {
	for (let i = 0; i < nums.length; i++) {
		if (nums[i] === val) {
			nums.splice(i, 1);
			i--;
		}
	}
	return nums.length;
}