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:

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.

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:

// 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]);
}

---

要求我们把数组中等于某个数的元素全部“移除”，移除并不是真正的移除，可以把它们移到数组的末尾。

我的思路是，i指针从前往后扫，遇到一个等于val的（需要移除的）元素时，j从i+1开始找一个不等于val的，交换i,j指向的元素，i继续前进。
思路还是很简单，结果也正确，但是在计算新数组的长度时需要考虑较多cases，太麻烦，我就直接从末尾再往前找，直到找到一个不等于val的下标位置。ugly代码：

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

本代码提交AC，用时4MS，排名倒数也是在我的预料之中的。看过题解之后，不得不感慨自己还是太笨，过段时间再来刷一遍。

二刷。这题其实很简单，也相当于快慢指针，快指针j一直走，如果nums[j]!=val，则把nums[j]赋值给nums[i]，同时i也往前走；如果nums[j]==val，则i要停下来，相当于i这个位置指示了可以放合法元素的位置。完整代码如下：

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

本代码很简洁，提交AC，用时4MS。