[Leetcode]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.

例子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.

例子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.

解题思路

方法一

从例子中可以看出，返回的数组只看去除给定数字后的数组的长度对不对，不需要考虑筛选后长度后面的数字，同时也不要求数组相对顺序保持不对。所以可以采用前后双指针的思路，前面指针遍历数组，遇到要去除的数字就和尾指针对应的数字交换，由于尾指针时刻指向所需数组的最后一位，最后只需要返回 尾指针+1 作为数组长度即可。注意要判断交换后的数字需不需要去除，代码如下：

int removeElement(vector<int>& nums, int val) {

    int front = 0, back = nums.size() - 1;

    while (front <= back) {
        // make sure back pointer not pointing to a value to remove
        while (front < back && nums[back] == val) {
                back--;
        }

        if (nums[front] == val) {
            swap(nums[front], nums[back]);
            back--;
        }
        front++;
    }

    return back + 1;
}

时间复杂度：O(n)
空间复杂度：O(1)

方法二

同样是双指针的思路，可以用一个快指针扫描数组，只要不是要去除的数字就通过慢指针复制在数组的前面，这种方法的好处是还可以保持数字间的相对位置不变，代码如下：

int removeElement(vector<int>& nums, int val) {

    int count = 0;

    for (int i = 0; i < nums.size(); i++) {
        if (nums[i] != val) {
            nums[count] = nums[i];
            count++;
        }
    }

    return count;
}

时间复杂度：O(n)
空间复杂度：O(1)