【Hot 100 刷题计划】 LeetCode 75. 颜色分类 | C++ 两次遍历双指针法

LeetCode 75. 颜色分类

📌 题目描述

题目级别：中等

给定一个包含红色、白色和蓝色、共n个元素的数组nums，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
我们使用整数0、1和2分别表示红色、白色和蓝色。
必须在不使用库内置的sort函数的情况下解决这个问题。

• 示例 1:
  输入：nums = [2,0,2,1,1,0]
  输出：[0,0,1,1,2,2]

💡 破题思路：两次 Partition 划分

这道题最直观的解法，就是借用快速排序（Quick Sort）中划分区间（Partition）的思想。

因为总共只有三种数字，我们可以分两步走：

1. 第一趟扫描：准备左右两个指针。左指针找非0，右指针找0，然后把它们互换。这一趟结束后，所有的0都被推到了数组的最前面。
2. 第二趟扫描：再次初始化左右指针。左指针找非2，右指针找2，然后把它们互换。这一趟结束后，所有的2都被推到了数组的最后面。

经过这两步，头部的0和尾部的2都归位了，剩下的1自然就被挤在了数组的中间，排序完成！

💻 C++ 代码实现 (两次遍历法)

classSolution{public:voidsortColors(vector<int>&nums){intl=0,r=nums.size()-1;// 第一趟：把所有的 0 换到最左边while(l<r){while(l<r&&nums[l]==0)l++;while(l<r&&nums[r]!=0)r--;if(l<r){swap(nums[l],nums[r]);l++,r--;}}// 第二趟：把所有的 2 换到最右边l=0,r=nums.size()-1;while(l<r){// 注意这里：左指针只要不是 2 就往右走，不用管 0 和 1while(l<r&&nums[l]!=2)l++;while(l<r&&nums[r]==2)r--;if(l<r){swap(nums[l],nums[r]);l++,r--;}}}};