75. 颜色分类（C++实现）

75. 颜色分类（C++实现）

文章目录

• 题目
• 思路--三指针

题目

题目链接：75. 颜色分类）

---

思路–三指针

其实颜色分类就是对 0 1 2 这三个数字进行排序，但是排序都是有效率之分的，我们希望可以通过一种高效的方法去排序这三个数字，而不希望直接调用排序函数去排序！

---

思考以下：

nums = [2,0,2,1,1,0] 要排序改数组，那么结果为[0,0,1,1,2,2]

初始条件：

分三种情况考虑这个问题：

最终结果：

---

代码演示：

class Solution {
public:
	//交换函数
	void swap(int& x, int& y)
	{
		int temp = x;
		x = y;
		y = temp;
	}
	void sortColors(vector& nums) {
		//初始条件
		int cur = 0;
		int left = 0;
		int right = nums.size() - 1;
		//开始遍历
		while (cur <= right)
		{	//碰到2
			if (nums[cur] == 2){
				swap(nums[cur], nums[right--]);
			}
			//碰到0
			else if (nums[cur] == 0){
				swap(nums[cur++], nums[left++]);
			}
			碰到1
			else{
				cur++;
			}
		}
	}
};