75. 颜色分类
问题
给定一个包含红色、白色和蓝色，一共个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
此题中，我们使用整数 分别表示红色、白色和蓝色。
注意:
不能使用代码库中的排序函数来解决这道题。
示例:
【75.|75. 颜色分类】输入:进阶：
输出:
一个直观的解决方案是使用计数排序的两趟扫描算法。解法1（偷懒的办法） 进阶中给出了一种解决方案。两次循环就可以完成。
- 首先，迭代计算出0、1 和 2 元素的个数，然后按照0、1、2的排序，重写当前数组。
- 你能想出一个仅使用常数空间的一趟扫描算法吗？
代码1 java实现
class Solution {
public void sortColors(int[] nums) {
if (nums==null || nums.length<2) {
return;
}
//数组中0的数量
int i=0;
//数组中1的数量
int j=0;
//数组中2的数量不需要计算，因为当i与j都是0时，剩下的肯定都是2
//开始第一次循环，获取i与j
for(int n:nums) {
if (n==0) {
i++;
} else if (n==1) {
j++;
}
}
//开始第二次循环，将0，1，2重新写入数组
for(int l = 0;
l0) {
nums[l]=0;
} else if (j>0) {
nums[l] = 1;
} else {
nums[l] = 2;
}
}
}
}
解法2 这其实就是荷兰国旗算法。算法如下：
- 设置三个指针，，接下来循环时分为三种情况处理：
- 当时，交换与的值，并且
- 当时，不做任何处理，
- 当时，交换与的值，并且
还有一个需要注意的地方在于，就是循环的终止条件，如果没有思考清楚，那么很有可能就写成了，但是这种情况是错的。考虑这样一个输入数组,在第一轮的判断时，是走的如上第三种情况，这样在第二轮时就是1了，如果是的判断的话，那么这一步就跳出循环了。最终结果就是，第二个元素并没有参与到比较中来。所以循环的规则应该是。
代码2 java实现
class Solution {
public void sortColors(int[] nums) {
if (nums == null || nums.length < 2) {
return;
}
//三个指针的初始化，
int begin = 0, curr = 0, end = nums.length-1;
//循环的判断条件见解法中的说明
while (curr <= end){
//第一种情况
if (nums[curr] == 0) {
nums[curr] = nums[begin];
nums[begin] = 0;
curr++;
begin++;
} else if (nums[curr] == 1) {
//第二种情况
curr++;
} else {
nums[curr] = nums[end];
nums[end] = 2;
end--;
}
}
}
