LeetCode Remove Element

LeetCode Remove Element

Given an array and a value, 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 in place with constant memory.

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

Example:
Given input array nums = [3,2,2,3], val = 3

Your function should return length = 2, with the first two elements of nums being 2.


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

我的思路是,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,排名倒数也是在我的预料之中的。看过题解之后,不得不感慨自己还是太笨,过段时间再来刷一遍。

Leave a Reply

Your email address will not be published. Required fields are marked *