LeetCode75：颜色分类-C语言一次遍历求解

问题描述：

给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

示例:
输入: [2,0,2,1,1,0]
输出: [0,0,1,1,2,2]

思路分析：

1. 如果单纯用排序算法，则忽略了实际问题的条件：数组中只有三种元素，并且元素的位置已经有数；
2. 我第一次求解时两次遍历：第一遍找出0，与开始的元素进行交换；第二遍找出1，接着第一遍中已交换好的下标元素进行交换；
3. 考虑能不能一次遍历？引入两个指针:
   index0（初始值为0)，作用是遍历发现0时，与当前元素交换
   index2（初始值为numsSize-1），作用是发现2时，与当前元素交换

代码实现

//交换两元素，注意运用指针
void swap(int* a, int* b) {
    
	int temp;
	temp = *a;
	*a = *b;
	*b = temp;
}
void sortColors(int* nums, int numsSize) {
    
	//定义元素0的初始最左指针
	int index0 = 0;
	//定义当前指针
	int cur = 0;
	//定义元素2的初始最右指针
	int index2 = numsSize - 1;
	//判断循环条件，不要忘记是<=,否则最后一个元素的位置确定不了
	while (cur <=index2) {
    
		//发现元素0，交换完毕后两个指针都要增加，因为交换到cur的元素只能是1
		if (nums[cur] == 0) {
    
			swap(nums + cur, nums + index0);
			index0++;
			cur++;
		}
		//发现元素2，交换完注意cur指针不能增加，因为从cur之后交换过来的元素可能是0，需要再次判断cur指向的值
		else if (nums[cur] == 2) {
    
			swap(nums + cur, nums + index2);
			index2--;
		}
		//发现元素1，直接后移当前指针
		else
			cur++;
    }
}

复杂度分析

1. 时间复杂度：由于只进行了一次遍历，故为O(n)；
2. 空间复杂度：由于没有额外利用数组以外的空间，故为O(1)。