public class SortColors {
/**
* 从左往右遍历，如果遇到0，左边肯定先是一堆0，然后是1堆1，交换过后，当前肯定是1，所以要i++。
* 如果遇到2，肯定往右交换，然后交换后的数未知，所以i不能轻举妄动
*/
// 时间复杂度O(n)，扫一遍
public void sortColors3(int[] nums) {
int zero = -1, two = nums.length;
for (int i = 0; i < two; ) {
if (nums[i] == 0) {
swap(nums, ++zero, i++);
} else if (nums[i] == 2) {
swap(nums, --two, i);
} else {
i++;
}
}
}
private void swap(int[] nums, int i, int j) {
int k = nums[i];
nums[i] = nums[j];
nums[j] = k;
}
/**
* 如果要扩展到k个颜色，如果颜色为0~k
* 原理很简单，就是统计每个颜色的个数，转成负数，保存在原来的数组中
* 统计完后再根据个数设置数组
* 其实可以另外开辟一个数组保存个数，如果对空间没有要求的话
*/
public void sortKColors(int[] colors, int k) {
for (int i = 0; i < colors.length; i++) {
while (colors[i] >= 0) {
int color = colors[i];
if (colors[color] >= 0) {
colors[i] = colors[color];
colors[color] = -2;
} else {
colors[color]--;
colors[i] = -1;
}
}
}
for (int i = colors.length - 1; i >= 0; ) {
int color = --k, count = -(colors[color] + 1);
for (int j = 0; j < count; j++) {
colors[i--] = color;
}
}
}
/**
* http://www.lintcode.com/zh-cn/problem/sort-colors-ii/
*/
// 如果颜色从1~k，lint
public void sortColors2(int[] colors, int k) {
// write your code here
for (int i = 0; i < colors.length; i++) {
while (colors[i] > 0) {
int color = colors[i];
if (colors[color - 1] > 0) {
colors[i] = colors[color - 1];
colors[color - 1] = -1;
} else {
colors[color - 1]--;
colors[i] = 0;
}
}
}
int color = k - 1;
for (int i = colors.length - 1; i >= 0; ) {
for (int j = 0; j < -colors[color]; j++) {
colors[i--] = color + 1;
}
color--;
}
}
}