Remove Element

发表于   |   分类于 ，

Given an array and a value, remove all instances of that value in place and return the new length.
Do not allocate extra space for another array, you must do this in place with constant memory.
The order of elements can be changed. It doesn’t matter what you leave beyond the new length.

Example:
Given input array nums = [3,2,2,3], val = 3
Your function should return length = 2, with the first two elements of nums being 2.

Hint:

  • Try two pointers.
  • Did you use the property of “the order of elements can be changed”?
  • What happens when the elements to remove are rare?

描述

删除数组内指定的元素，并且不能使用额外的空间

分析

因为不能使用额外的空间，所以在原数组内操作。

一般方法：采用 i，j 两个下标，利用 j 来遍历数组，过滤掉指定元素，将其余元素放置在 i 下标。

优化方法（减少赋值操作的次数，在指定元素出现次数少的情况下尤其明显，适用于可以打乱数组元素顺序的情况）：遍历数组，将指定元素与数组最后一个元素交换，同时缩短数组长度。

代码

一般方法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class Solution {
    public int removeElement(int[] nums, int val) {

        int i = 0;
        int n = nums.length;

        for (int j = 0; j < n; j++) {
            if (nums[j] != val) {
                nums[i++] = nums[j];
            }
        }

        return i;
    }
}

优化方法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class Solution {
    public int removeElement(int[] nums, int val) {

        int i = 0;
        int n = nums.length;

        while (i < n) {
            if (nums[i] == val) {
                nums[i] = nums[n - 1];
                n--;
            } else {
                i++;
            }
        }

        return i;
    }
}