双指针法-删除数组中的重复元素以及奇偶排序

1.1双指针法简介——原地排序

双指针法，即一个快指针和一个慢指针，快指针提前遍历数组元素，慢指针停在被处理元素位置。可以用数组的索引$i,j$i,j实现双指针算法。

1.2删除数组中的重复元素

1.2.1解题思路

给定数组是有序的（若无序，首先调用排序，当然输出的元素也是有序的），那么重复的元素一定会相邻。要求删除重复元素，实际上就是将不重复的元素移到数组的左侧，最后返回不重复元素的个数即可。$p$p为慢指针，$q$q为快指针，$p，q$p，q可以理解为数组的索引。
1.比较 $p$p 和 $q$q 位置的元素是否相等。
（1）如果相等，$q$q 后移 1 位， $p$p 保持不动。
（2）如果不相等，将$q$q位置的元素复制到 $p+1$p+1 位置上，$p$p 后移一位，$q$q 后移 1 位
2.重复上述过程，直到$q$q 等于数组长度。
返回 $p+1$p+1，即为新数组长度。

1.2.2实现代码(C++)

	int removeDuplicates(vector<int>& nums)
	{
		int p = 0;
		for (int q = 1; q < nums.size(); q++)
		{
			if (nums[p] != nums[q])
			{
				nums[++p] = nums[q];
			}
		}
		return ++j;
	}

若用C语言实现，将数组的定义形式改变和传入数组长度即可。
复杂度分析
时间复杂度：$O(n)$O(n)，假设数组的长度是 $n$n，那么 $i$i和 $j$j 分别最多遍历 $n$n步。
空间复杂度：$O(1)$O(1)。

1.3奇偶排序

1.3.1问题描述

给定一个非负整数数组 A，返回一个数组，在该数组中， A 的所有偶数元素在最左边，所有奇数元素在最右。
例如
输入：$[3,1,2,4]$[3,1,2,4]
输出：$[2,4,3,1]$[2,4,3,1]
输出$[4,2,3,1]，[2,4,1,3] 和 [4,2,1,3]$[4,2,3,1]，[2,4,1,3]和[4,2,1,3]也会被接受。

1.3.2解题思路

从上述的删除数组的重复元素可以看出，$p,q$p,q指针均在数组最前面，对于奇偶排序，则是将$p$p放在数组最前面，$q$q指针放在数组最后面，采用对2取余判断出奇偶数。
在指针移动的过程中两个指针取余的结果记为$(p\%2,q\%2)$(p%2,q%2)，则有如下四种情况：

如果是 (0, 1)，那么万事大吉 i++ 并且 j–。
如果是 (1, 0)，那么交换两个元素，然后继续。
如果是 (0, 0)，那么说明 i 位置是正确的，只能 i++。
如果是 (1, 1)，那么说明 j 位置是正确的，只能 j–。

1.3.3实现代码

	vector<int> sortArrayByParity(vector<int>& A) 
	{
		int i = 0;
		int j = A.size() - 1;
		int temp;
		while (i < j)
		{
			if ((A[i] % 2) > (A[j] % 2))
			{
				temp = A[i];
				A[i] = A[j];
				A[j] = temp;
			}
			if (A[i] % 2 == 0)
			{
				i++;
			}
			if (A[j] % 2 == 1)
			{
				j--;
			}
		}
		return A;
	}