GuilinDev

Lc0027

05 August 2008

27 - Remove Element

原题概述

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:

1
2
3
4
5

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:

1
2
3
4
5
6
7

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.

Clarification:

Confused why the returned value is an integer but your answer is an array?

Note that the input array is passed in by reference, which means modification to the input array will be known to the caller as well.

Internally you can think of this:

1
2
3
4
5
6
7
8

// nums is passed in by reference. (i.e., without making a copy)
int len = removeElement(nums, val);

// any modification to nums in your function would be known by the caller.
// using the length returned by your function, it prints the first len elements.
for (int i = 0; i < len; i++) {
    print(nums[i]);
}

题意和分析

这道题很简单，与283 - Move Zeros类似，只不过只管左边不用swap值，in place的做法就是把非val的值找出来全部排到原Array的前面，用一个index来记录位置，最后返回index的位置就是除去val的数组的长度。

整个数组扫一遍，Time：O(n)

注意：按照题意，这样的处理方式改变了数组里面的元素顺序。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

class Solution {
  public int removeElement(int[] nums, int val) {
    if (nums == null || nums.length == 0) {
      return 0;
    }

    int slow = 0;
    for (int fast = 0; fast <= nums.length - 1; fast++) { //[0...nums.length - 1]
      if (nums[fast] != val) {//找到不同等于val的值就排到nums的左边去，然后递增准备存储下一个非val的元素
        if (slow != fast) { //优化下让自己跟自己不要赋值，例如[1,2,3,4,5]
          nums[slow] = nums[fast];
        }
        slow++;
      }
    }
    return slow;
  }
}
This site is open source. Improve this page.