原题
给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
注意:
不能使用代码库中的排序函数来解决这道题。
示例:
输入: [2,0,2,1,1,0] 输出: [0,0,1,1,2,2]
进阶：
- 一个直观的解决方案是使用计数排序的两趟扫描算法。
首先，迭代计算出0、1 和 2 元素的个数，然后按照0、1、2的排序，重写当前数组。 - 你能想出一个仅使用常数空间的一趟扫描算法吗？
解法
思想
计数排序算是这类问题的通解吧。。不过对于仅有两种或三种元素，可以使用交换方法来解。
代码
计数：
class Solution {
public void sortColors(int[] nums) {
int count0 = 0,count1 = 0,count2 = 0;
for(int i:nums){
if(i == 0) count0++;
else if(i == 1) count1++;
else count2++;
}
for(int i = 0;i<nums.length;i++){
if(i<count0) nums[i] = 0;
else if(i<count0+count1) nums[i] = 1;
else nums[i] = 2;
}
}
}
三指针交换：
class Solution {
public void sortColors(int[] nums) {
int p0 = 0, cur = 0;
int p2 = nums.length - 1;
int tmp;
while (cur <= p2) {
if (nums[cur] == 0) {
tmp = nums[p0];
nums[p0++] = nums[cur];
nums[cur++] = tmp;
}
else if (nums[cur] == 2) {
tmp = nums[cur];
nums[cur] = nums[p2];
nums[p2--] = tmp;
}
else cur++;
}
}
}
原创文章，作者：彭晨涛，如若转载，请注明出处：https://www.codetool.top/article/leetcode75-%e9%a2%9c%e8%89%b2%e5%88%86%e7%b1%bb/
