题目描述（简单难度）

27. Remove Element - 图1

和上一题类似，只不过这个是去除给定的值，看起来还更简单些。

例如给了 nums = [ 3, 2, 2, 3 ]，val = 3， 然后我们返回 len = 2，并且 nums 修改为 [ 2, 2 ] 。

解法一

和上道题一样，我们利用快慢指针，此外我们还得用下反向的思维。快指针 fast 和慢指针 slow，一直移动 fast ，如果 fast 指向的值不等于给定的 val ，我们就将值赋给 slow 指向的位置，slow 后移一位。如果 fast 指向的值等于 val 了，此时 fast 后移一位就可以了，不做其他操作。

  1. public int removeElement(int[] nums, int val) {
  2.     int fast = 0;
  3.     int slow = 0;
  4.     while (fast < nums.length) {
  5.         if (nums[fast] != val) {
  6.             nums[slow++] = nums[fast];
  7.         }
  8.         fast++;
  9.     }
  10.     return slow;
  11. }

时间复杂度：O（n）。

空间复杂度：O（1）。

解法二

参考给出的Soloution。

上边的解法，我们是如果不等于 val 就赋值。但如果按题目的想法，应该是如果等于 val 就移除。我们从正方面去想，也就是等于 val 的话，我们怎么体现移除呢？

题目中有个说明我们没利用到，他告诉我们说 the order of those five elements can be arbitrary，就是说数组的顺序可以随便换，我们怎么充分利用呢？

我们可以这样，如果当前元素等于 val 了，我们就把它扔掉，然后将最后一个值赋值到当前位置，并且长度减去 1。什么意思呢？

比如 1 2 2 4 6，如果 val 等于 2 。那么当移动到 2 的时候，等于 val 了。我们就把最后一个位置的 6 赋值过来，长度减去 1 。就变成了 1 6 2 4。完美！达到了移除的效果。然后当又移动到新的 2 的时候，就把最后的 4 拿过来，变成 1 6 4，达到了移除的效果。看下代码吧。

  1. public int removeElement(int[] nums, int val) {
  2.     int i = 0;
  3.     int n = nums.length;
  4.     while (i < n) {
  5.         if (nums[i] == val) {
  6.             nums[i] = nums[n - 1]; 
  7.             n--;
  8.         } else {
  9.             i++;
  10.         }
  11.     }
  12.     return n;
  13. }

时间复杂度：同样是 O（n），但如果等于 val 的值比较少，解法二会更有效率些。比如 1 2 3 4，val = 2。解法一 while 循环中将调用 3 次赋值。而解法二中，仅仅当等于 val 的时候赋值 1 次。

空间复杂度：O（1）。

总

Solution 给出的想法让人耳目一新，对于移除的值少的情况，优化了不少。

windliang wechat

添加好友一起进步~

如果觉得有帮助的话，可以点击 这里 给一个 star 哦 ^^

如果想系统的学习数据结构和算法，强烈推荐一个我之前学过的课程，可以点击 这里 查看详情