题目描述

英文

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.

中文

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

不要使用额外的数组空间,你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。

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

示例 1:

给定 nums = [3,2,2,3], val = 3,

函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。

你不需要考虑数组中超出新长度后面的元素。

示例 2:

给定 nums = [0,1,2,2,3,0,4,2], val = 2,

函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。

注意这五个元素可为任意顺序。

你不需要考虑数组中超出新长度后面的元素。

解法一

思路

这题需要原地移除数组中值等于val的元素,需要注意的是空间复杂度需要是O(1),并且不要求移除val后数组中元素顺序不变。那么这题其实就可以理解为“把值为val的元素全部移到数组尾部,且数组元素顺序可以改变”。

注意“顺序可以改变”这个说法,让这题的难度降低了不少。这里介绍一种双指针的做法:

  1. 头指针初始指向数组第一个元素,尾指针初始指向数组最后一个元素。
  2. 头指针从前往后扫描,遇到第一个val时停下。
  3. 尾指针从后往前扫描,遇到第一个非val时停下。
  4. 交换头尾指针所指元素。
  5. 按2-4循环直到头尾指针相遇,相遇点元素下标即为新的数组长度。

想想为什么相遇点元素下标即为新的数组长度?因为头尾指针相遇点一定是“将所有val移到数组尾部”后的“第一个”val,即此时两个指针指向新数组的后一个元素,其下标就正好是新数组的长度了。

这样整个算法只需要头尾两个指针变量,和元素交换时的一个临时变量,实现了O(1)的时间复杂度。

以示例2的nums = [0,1,2,2,3,0,4,2]val = 2来举例:

0 1 2 2 3 0 4 2
^             ^

0 1 2 2 3 0 4 2
    ^       ^

0 1 4 2 3 0 2 2
    ^       ^

0 1 4 2 3 0 2 2
      ^   ^

0 1 4 0 3 2 2 2
      ^   ^

0 1 4 0 3 2 2 2
          ^
          ^

output: 0 1 4 0 3

Python

class Solution(object):
    def removeElement(self, nums, val):
        """
        :type nums: List[int]
        :type val: int
        :rtype: int
        """
        i = 0
        j = len(nums) - 1
        while i <= j:
            if nums[i] != val:
                i += 1
            elif nums[j] == val:
                j -= 1
            else:
                nums[i], nums[j] = nums[j], nums[i]
        return i

Java

public class Solution {
    public int removeElement(int[] nums, int val) {
        int i = 0;
        int j = nums.length - 1;
        while (i <= j) {
            if (nums[i] != val) {
                i++;
            } else if (nums[j] == val) {
                j--;
            } else {
                int temp = nums[i];
                nums[i] = nums[j];
                nums[j] = temp;
            }
        }
        return i;
    }
}

C++

class Solution {
public:
    int removeElement(vector<int> &nums, int val) {
        int i = 0;
        int j = nums.size() - 1;
        while (i <= j) {
            if (nums[i] != val) {
                i++;
            } else if (nums[j] == val) {
                j--;
            } else {
                int temp = nums[i];
                nums[i] = nums[j];
                nums[j] = temp;
            }
        }
        return i;
    }
};