前端刷题路-Day38：移除元素（题号27）-一一网

这是我参与更文挑战的第2天，活动详情查看：更文挑战

移除元素（题号27）

题目

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

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

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

说明:

为什么返回数值是整数，但输出的答案是数组呢?

请注意，输入数组是以「引用」方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。

你可以想象内部操作如下:

// nums 是以“引用”方式传递的。也就是说，不对实参作任何拷贝
int len = removeElement(nums, val);

// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中 该长度范围内 的所有元素。
for (int i = 0; i < len; i++) {
    print(nums[i]);
}
复制代码

示例 1：

输入：nums = [3,2,2,3], val = 3
输出：2, nums = [2,2]
解释：函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。你不需要考虑数组中超出新长度后面的元素。例如，函数返回的新长度为 2 ，而 nums = [2,2,3,3] 或 nums = [2,2,0,0]，也会被视作正确答案。
复制代码

示例 2：

输入：nums = [0,1,2,2,3,0,4,2], val = 2
输出：5, nums = [0,1,4,0,3]
解释：函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。注意这五个元素可为任意顺序。你不需要考虑数组中超出新长度后面的元素。
复制代码

提示：

0 <= nums.length <= 100
0 <= nums[i] <= 50
0 <= val <= 100

链接

leetcode-cn.com/problems/re…

解释

这题有点不太好理解，所以要好好看题目。

重点在说明里面，说明了详细解释了为什么返回时一个数字，输出却是一个数组。

也就是返回的是一个长度，输出的时候会截取数组从0到当前长度的元素，调用的话可以理解为是这样的?：

var nums = [2, 2, 3]

var removeElement = function(nums, val) {
  // Todo
};

var count = removeElement(nums, 2)
console.log(nums.slice(0, count))
复制代码

count就是函数的返回值，那么输出就是nums.slice(0, count)，所以输出是一个数组。

这就涉及到这题的另外一个重点了，那就是在原数组的基础上进行改变，也就是说不能对nums进行赋值操作，只能更改nums内部的值。

如果不是在原数组的基础上进行修改，那么最后输出的nums会和函数中的nums不是一个东西，导致输出错误。

了解题目的意思之后就应该知道怎么怎么做了，总共只需要两步操作：

把数组中符合条件的值都挪到后面或者前面
获取到重复元素的个数，进行最后的返回判断

这里的实际操作其实很简单，只是笔者没想到那块去，最后还是暴力解法解出来了，但并不是最优的。

自己的答案（暴力）

看到暴力求解相信大家应该也都知道是怎样的一个操作了，笔者这里首先将所有符合条件的元素替换成固定的一个字符串，这里是'fun'。

之后对数组进行排序操作，使用sort()方法对数组进行原地排序，因为sort()默认的排序方法是将元素转化成字符串后根据其UTF-16代码单元值序列进行排序。简单来说就是数字会在前面，字符串会在后面。

那么此时所有符合条件的值就都在数组后面的，剩下的就是进行迭代操作，不断取数组最后一个值，如果是'fun'就pop()掉，直到去掉所有的'fun'。

最后返回nums的length即可。

代码?：

/**
 * @param {number[]} nums
 * @param {number} val
 * @return {number}
 */
var removeElement = function(nums, val) {
    for (let i = 0; i < nums.length; i++) {
        nums[i] = nums[i] === val ? 'fun' : nums[i]
    }
    nums.sort()
    while(nums[nums.length - 1] === 'fun') {
        nums.pop()
    }
    return nums.length
};
复制代码

后续笔者又进行了一些优化，发现其实并不需要pop()掉所有符合条件的元素，只需要知道符合条件的元素的个数即可，最后返回数组的原长度减去这个个数即可，所以代码变成了这样?：

/**
 * @param {number[]} nums
 * @param {number} val
 * @return {number}
 */
var removeElement = function(nums, val) {
    var count = 0
    for (let i = 0; i < nums.length; i++) {
        if (nums[i] === val) {
            nums[i] = 'fun'
            count++
        }
    }
    nums.sort()
    return nums.length - count
};
复制代码

性能上有一丢丢的提升，但本质上依然是暴力解法，不推荐。

更好的方法（替换）

替换这个方法的思路有点清奇，简单来说就是获取到所有符合田间的元素的，将它们依次放入数组中，同时累计符合条件元素的个数。

此时数组的元素已经被改变了，直接返回符合条件元素的个数即可。

var removeElement = function(nums, val) {
  var ans = 0
  for (const num of nums) {
    if (num !== val) {
      nums[ans] = num
      ans++
    }
  }
  return ans
};
复制代码

不得不说思路还是很好的，写起来也很简单。

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

更好的方法（双指针）

双指针的思路就是官方推荐的思路了，从元素的两头开始调整，如果左指针的树符合条件，那么就和右指针的数进行替换操作，然后右指针往左挪一位，左指针不动，继续迭代。

笔者一开始也想到这种方法，其核心就是将符合条件的数都挪到数组的右侧，可一直没有避免右侧本身就有符合条件的数的问题，原因就是当右侧数符合条件时，替换之后的左侧树也是符合条件的，笔者这里没有做适当的处理，导致一直失败，其实解决方案很简单，只要不动左侧数，再走一遍判断条件即可。

代码?：

function removeElement(nums, val) {
  var left = 0
      right = nums.length
  while (left < right) {
    if (nums[left] === val) {
      nums[left] = nums[right - 1]
      right--
    } else {
      left++
    }
  }
  return left
}
复制代码

这里有两点需要注意：

首先是当右侧数被替换后，不要动左指针，只动右指针，让左指针的数再走一次判断，因为右指针的数有可能也是符合条件的数。
注意这里右指针的初始化赋值是nums.length而不是nums.length - 1。

这样做的原因是为了处理某些特殊用例，比方说?：
```
[3,2,2,3]  3
复制代码
```
这里如果右指针的初始化值为nums.length - 1，你会发现在while里面只走了三次，但其实应该走4次的，这是因为数组整体长度的问题，如果不明白可以打印几次迭代的结果即可。