问题

Given an array nums and a value val, 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 by modifying the input array in-place with O(1) extra memory.

The order of elements can be changed. It doesn’t matter what you leave beyond the new length.

Example 1:

Given nums = [3,2,2,3], val = 3,
Your function should return length = 2, with the first two elements of nums being 2.
It doesn’t matter what you leave beyond the returned length.

Example 2:

Given nums = [0,1,2,2,3,0,4,2], val = 2,
Your function should return length = 5, with the first five elements of nums containing 0, 1, 3, 0, and 4.
Note that the order of those five elements can be arbitrary.
It doesn’t matter what values are set beyond the returned length.

  • Level: Easy

解题思路

如果没有O(1)的空间复杂度，并且不关注修改后原来数组的结果。我们可以利用set或者map来解决此题。现在题目既然要求O(1)的空间复杂度解决，那么可以使用“双指针”的思路来解决此题,具体思路如下：

  1. 设pos为新数组下标值，初始化为0；idx为原数组的下标，[1, n);
  2. 若arr[pos] != arr[i],则 arr[pos++] = arr[i]
  3. 重复2，直到 i = n;
  4. 返回 新数组的长度：pos+1

详细代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
public int removeElement(int[] nums, int val) {
    if (null == nums || nums.length <= 0) {
        return 0;
    }
    int len = nums.length;
    int pos = 0;
    for (int idx = 1; idx < len; ++idx) {
        if (nums[pos] != val) {
            nums[++pos] = nums[idx];
        }
    }
    return (pos + 1);
}

第一种解法保留了元素在数组中的顺序，题目也说明了可以改变数组的元素的位置，那么我们可以使用最后一位
元素来替换重复的元素。相关的代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public int removeElement2(int[] nums, int val) {
    if (null == nums || nums.length <= 0) {
        return 0;
    }
    int len = nums.length;
    int idx = 0;
    while (idx < len) {
        if (nums[idx] == val) {
            nums[idx] = nums[len-1];
            --len;
        } else {
            ++idx;
        }
    }
    return len;
}

复杂度分析

两种算法时间复杂度和空间复杂度如下：

  • 时间复杂度为O(n),其中n为排序数组的长度；
  • 空间复杂度为O(1)