数组删除元素

在数组中删除值为val的元素，因为数组在内存中是连续存储，所以不能只删除元素，而是在删除元素后还要使后边元素前移。

在数组中删除元素有两种方法：

（1）暴力解法

（2）双指针法

1.暴力解法

暴力解法就是通过两层循环，一个for循环遍历数组，一个for循环在删除后更新数组。实现代码如下：

//移除元素
//Solution1 --暴力求解 
int removeElement(vector<int>& nums, int val){
	int l = nums.size();
	for (int i = 0; i<l; i++){
		if (nums[i] == val) {
			for (int j = i+1; j<l; j++) {
				nums[j-1] = nums[j];
			}
			i --;
			l--; 
		}
	}
	return l;
}

暴力解法时间复杂度为O(n^2)，空间复杂度为O(1)。

2.双指针法（快慢指针法）

双指针法是通过一个快指针和一个慢指针在一个for循环下完成两个for循环的工作。

//Solution2 --双指针法
int removeElement(vector<int>& nums, int val) {
	int slowIndex = 0;
	for (int fastIndex = 0; fastIndex < nums.size(); fastIndex++) {
		if (val != nums[fastIndex]) {
			nums[slowIndex++] = nums[fastIndex];
		}
	}
	return slowIndex;
}

双指针法时间复杂度为O(logn)，空间复杂度为O(1)。