力扣75——颜色分类
原题
给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
注意:
不能使用代码库中的排序函数来解决这道题。
示例:
输入: [2,0,2,1,1,0]
输出: [0,0,1,1,2,2]
进阶：
* 一个直观的解决方案是使用计数排序的两趟扫描算法。
首先，迭代计算出0、1 和 2 元素的个数，然后按照0、1、2的排序，重写当前数组。
* 你能想出一个仅使用常数空间的一趟扫描算法吗？
原题url：https://leetcode-cn.com/problems/sort-colors/
解题
两趟扫描
我当时想到的第一种想法就是排序，后来感觉没有必要，因为只有3种元素，我完全就可以按照进阶提示中的第一条，先扫描统计出各元素个数，然后第二遍扫描时，直接进行赋值。
让我们直接来看代码：
class Solution {
public void sortColors(int[] nums) {
// 记录0,1,2的个数
int num0 = 0, num1 = 0, num2 = 0;
// 计算各个数字出现的次数
for (int i : nums) {
switch(i) {
case 0:
num0++;
break;
case 1:
num1++;
break;
case 2:
num2++;
break;
}
}
// 重新赋值
for (int i = 0; i < nums.length; i++) {
if (i < num0) {
nums[i] = 0;
} else if (i < num0 + num1) {
nums[i] = 1;
} else {
nums[i] = 2;
}
}
}
}
提交OK，执行用时：0 ms，内存消耗：35.2 MB。是否还可以优化呢？
优化
参考进阶提示中的第二条，上面的方法使用了常数空间，但一遍扫描该如何做到呢？
我其实并没有想出来，参考了别人的解法：利用三个指针进行一次遍历并交换。
具体来说，就是增加一个当前指针current（从下标0开始）、一个指向数字0区间的末尾指针p0（从下标0开始）、一个指向数字2区间的开始指针p2（从下标 nums.length - 1）。下标0 到下标 p0 之间存放数字0，下标 p0 到 p2 之间存放数字1，下标 p2 到 下标 (nums.length - 1) 之间存放数字2。current 指针从下标0开始遍历，如果值为0，则和 p0 交换，如果值为2，则和 p2 交换。
让我们来看看代码：
class Solution {
public void sortColors(int[] nums) {
// 利用3个指针current、p0、p2
int current = 0, p0 = 0, p2 = nums.length - 1;
while (current <= p2) {
// 如果当前值为1，current指针往后移动
if (nums[current] == 1) {
current++;
continue;
}
// 如果当前值为0，则和 p0 交换，p0指针往后移动
if (nums[current] == 0) {
nums[current] = nums[p0];
nums[p0] = 0;
// 因为p0一开始和current相同
if (p0 == current) {
current++;
}
p0++;
continue;
}
// 如果当前值为2，则和 p2 交换，p2指针往前移动
if (nums[current] == 2) {
nums[current] = nums[p2];
nums[p2] = 2;
p2--;
continue;
}
}
}
}
提交OK，执行用时：0 ms，内存消耗：35 MB。这结果，感觉好像没有多少优化，但对于我们而言，最重要的是增加了一种解题思路。
总结
以上就是这道题目我的解答过程了，不知道大家是否理解了。这道题主要在于利用指针一遍扫描得出结果，优化解题。
有兴趣的话可以访问我的博客或者关注我的公众号，说不定会有意外的惊喜。
https://death00.github.io/