【数组】移除元素

题目链接：移除元素
关键点：
【1】不能使用额外的数组空间；
【2】不需要考虑数组中超出新长度后面的元素。
思路：数组的存储空间是连续的，不能直接删除某个元素，只能选择覆盖，因此最简单直接的办法就是每遇到需要移除的元素就将它后面的所有元素向前移动一位。这里有两种解法，一种是暴力解法，一种是双指针解法。
1）暴力解法

#include <iostream>
#include <vector>

class Solution
{
public:
	int removeElement(std::vector<int>& nums, int val)
	{
		int size = nums.size();
		for (int i = 0; i < size; ++i)				// 遍历nums,取出每个数
		{
			if (nums[i] == val)						// 如果发现需要移除的元素
			{
				for (int j = i + 1; j < size; ++j)	// 遍历需要移除元素的下一个元素到最后一个元素[i+1,size）
				{
					nums[j - 1] = nums[j];			// 将需移除的元素后所有的元素前移一位
				}
				--i;								// 原来下标为i的元素都向前移动了1位，因此需要-1
				--size;								// 数组有效长度-1（不需要考虑数组中超出新长度后面的元素）
			}
		}
		return size;
	}
};

int main()
{
	std::vector<int> nums = { 1,2,3,4,5,3,3,8,9 };
	Solution s;
	int ret = s.removeElement(nums, 3);
	std::cout << ret << std::endl;
	return 0;
}

2）双指针法(快慢指针法)
首先快慢指针同时指向第一个元素，然后同步向后移动，用快指针判断元素，慢指针来存储，快指针每次拿到不是删除的元素时就赋给慢指针。

#include <iostream>
#include <vector>

class Solution
{
public:
	int removeElement(std::vector<int>& nums, int val)
	{
		int left = 0;	
		for (int right = 0; right < nums.size(); right++)
		{
			if (nums[right] != val)							// 如果不是需要删除的元素，就往数组中填
			{
				nums[left++] = nums[right];
			}
		}
		return left;										// Left的值就是最终数组的大小
	}
};

int main()
{
	std::vector<int> nums = { 1,2,3,4,5,3,3,8,9 };
	Solution s;
	int ret = s.removeElement(nums, 3);
	std::cout << ret << std::endl;
	return 0;
}