解
第一步，万年不变的查错。如果给的array是null或不够两个数，直接return 0
public void sortColors2(int[] colors, int k) {
if (nums == null || nums.length < 2) {
return 0;
}
...
}
跟上一个颜色分类的题非常像，只不过由3个颜色增加到了k个颜色，所以不能用哪种简单的双指针去解了。但是计数排序依然可以用。先来个计数排序的答案。
首先找出每个数字出现的个数。这里用的k+1个，因为这次颜色是从1开始的，与其每次减一加一，倒不如跳出0，从1开始。
int[] count = new int[k + 1];
for (int color : colors) {
count[color]++;
}
然后把count遍历一遍，覆盖原array就可以了。
for (int i = 0; i < count.length; i++) {
for (int j = 0; j < count[i]; j++) {
color[current++] = i;
}
}
完整的code
public class Solution {
/*
* @param colors: A list of integer
* @param k: An integer
* @return: nothing
*/
public void sortColors2(int[] colors, int k) {
if (colors == null || colors.length < 2) {
return;
}
int[] count = new int[k + 1];
for (int color : colors) {
count[color]++;
}
int current = 0;
for (int i = 1; i < count.length; i++) {
for (int j = 0; j < count[i]; j++) {
colors[current++] = i;
}
}
}
}
解2
这里已经不能做到像颜色分类那样，双指针单次遍历就完成了。这里九章的答案用到了rainbowSort，但其实我觉得就是改动过的quickSort。
public void sortColors2(int[] colors, int k) {
if (nums == null || nums.length < 2) {
return 0;
}
sort(colors, 0, colors.length - 1, 1, k);
}
private void sort(int[] colors, int start, int end, int colorFrom, int colorTo) {
....
}
这里跟quickSort的开始是一样的，quickSort因为需要recursion，而且parameter不一样，所以单独一个method。colorFrom跟colorTo用来决定中间的颜色。
首先是exit condition，即如果start到了end，或开始的颜色和结束的颜色是一样的，就结束。
if (start >= end || colorFrom == colorTo) {
return;
}
然后跟quickSort一样，左边从start开始，右边从end开始，不同的是中间不是由start跟end决定的，而是colorFrom和colorTo。
int left = start;
int right = end;
int mid = colorFrom + (colorTo - colorFrom) / 2;
然后只要是小于等于中间的颜色的就放到左边，大于中间颜色的就放到右边。最后再各自去递归的排左右两半。
while (left <= right) {
while (left <= right && colors[left] <= colorMid) {
left++;
}
while (left <= right && colors[right] > colorMid) {
right--;
}
if (left <= right) {
swap(colors, left, right);
}
}
sort(colors, start, right, colorFrom, colorMid);
sort(colors, left, end, colorMid + 1, colorTo);
完整的code
public class Solution {
/*
* @param colors: A list of integer
* @param k: An integer
* @return: nothing
*/
public void sortColors2(int[] colors, int k) {
if (colors == null || colors.length < 2) {
return;
}
sort(colors, 0, colors.length - 1, 1, k);
}
private void sort(int[] colors, int start, int end, int colorFrom, int colorTo) {
if (start >= end || colorFrom == colorTo) {
return;
}
int left = start;
int right = end;
int colorMid = colorFrom + (colorTo - colorFrom) / 2;
while (left <= right) {
while (left <= right && colors[left] <= colorMid) {
left++;
}
while (left <= right && colors[right] > colorMid) {
right--;
}
if (left <= right) {
swap(colors, left, right);
}
}
sort(colors, start, right, colorFrom, colorMid);
sort(colors, left, end, colorMid + 1, colorTo);
}
private void swap(int[] nums, int a, int b) {
int temp = nums[a];
nums[a] = nums[b];
nums[b] = temp;
}
}
分析
时间复杂度
第一个方法，依然是遍历两次，所以是O(n)。第二个方法，大概就是quickSort，所以O(nlogn)，不过不同在于使用颜色来分开，而颜色最多有k个，所以准确说应该是O(nlogk)，因为每次都可以分开一半的颜色。相比之下第一个方法要快很多。
空间复杂度
第一个方法需要O(n)的额外空间，用来存放每个颜色的数量。第二个方法是常数额外空间，O(1)。在空间上来说，第二种方法更好。
总的来说，看到这个题，应该先给第一个答案。第一个答案用快用简单。如果面试官要求用O(1)的空间，再去给第二个方法。
