75. 分类颜色
描述
- 给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
- 此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
- 注意：不能使用代码库中的排序函数来解决这道题。
示例:
输入: [2,0,2,1,1,0]
输出: [0,0,1,1,2,2]
进阶：
一个直观的解决方案是使用计数排序的两趟扫描算法。
首先，迭代计算出0、1 和 2 元素的个数，然后按照0、1、2的排序，重写当前数组。
你能想出一个仅使用常数空间的一趟扫描算法吗？
思路
- 两趟扫描算法也是一个很不错的思路，有时候排序不一定是要基于交换的，重构也是一种排序的方式。
- 最优解用 3 个指针分别标记已排好序部分最后一个 0、1、2。当遍历到新元素时，将对应元素的下一个元素置为所需元素即可，具体如下：(参考)
1）t0,t1,t2 初始均为 -1；
2）若当前元素为 0，则将 t2 的下一个元素置为 2，t1 的下一个元素置为 1，t0 的下一个元素置为 0。由于初始时三者均指向同一位置，所以顺序一定要是 t2，t1，t0
3）若当前元素为 1，则将 t2 的下一个位置置为 2，t1 的下一个位置置为 1。
4）若当前元素为 2，则将 t2 的下一个位置置为 2。
- 最优解本质上就是将两次扫描算法的一次扫描、一次重写改进为了边扫描边重写。
class Solution {
public:
void sortColors(vector<int>& nums) {
if (nums.empty()) return;
int t0 = -1, t1 = -1, t2 = -1;
for (int i = 0; i < nums.size(); ++i) {
if (nums[i] == 0) {
nums[++t2] == 2;
nums[++t1] == 1;
nums[++t0] == 0;
} else if (nums[i] == 1) {
nums[++t2] == 2;
nums[++t1] == 1;
} else if (nums[i] == 2) {
nums[++t2] = 2;
}
}
}
};
