Sort Colors II
给定一个有n个对象(包括k种不同的颜色,并按照1到k进行编号)的数组,将对象进行分类使相同颜色的对象相邻,并按照1,2,...k的顺序进行排序。
样例
给出colors=[3, 2, 2, 1, 4],k=4, 你的代码应该在原地操作使得数组变成[1, 2, 2, 3, 4]
注意
不能使用代码库中的排序函数来解决这个问题
挑战
一个相当直接的解决方案是使用计数排序扫描2遍的算法。这样你会花费O(k)的额外空间。你否能在不使用额外空间的情况下完成?
题解
inplace,并且O(N)时间复杂度的算法。
我们可以使用类似桶排序的思想,对所有的数进行计数。
- 从左扫描到右边,遇到一个数字,先找到对应的bucket.比如 3 2 2 1 4 第一个3对应的bucket是index = 2 (bucket从0开始计算)
- Bucket 如果有数字,则把这个数字移动到i的position(就是存放起来),然后把bucket记为-1(表示该位置是一个计数器,计1)。
- Bucket 存的是负数,表示这个bucket已经是计数器,直接减1. 并把color[i] 设置为0 (表示此处已经计算过)
- Bucket 存的是0,与3一样处理,将bucket设置为-1, 并把color[i] 设置为0 (表示此处已经计算过)
- 回到position i,再判断此处是否为0(只要不是为0,就一直重复2-4的步骤)。 6.完成1-5的步骤后,从尾部到头部将数组置结果。(从尾至头是为了避免开头的计数器被覆盖)
例子(按以上步骤运算):
3 2 2 1 4
2 2 -1 1 4
2 -1 -1 1 4
0 -2 -1 1 4
-1 -2 -1 0 4
-1 -2 -1 -1 0
Code
class Solution {
/**
* @param colors: A list of integer
* @param k: An integer
* @return: nothing
*/
public void sortColors2(int[] colors, int k) {
if (colors == null) {
return;
}
int len = colors.length;
for (int i = 0; i < len; i++) {
// Means need to deal with A[i]
while (colors[i] > 0) {
int num = colors[i];
if (colors[num - 1] > 0) {
// 1. There is a number in the bucket,
// Store the number in the bucket in position i;
colors[i] = colors[num - 1];
colors[num - 1] = -1;
} else if (colors[num - 1] <= 0) {
// 2. Bucket is using or the bucket is empty.
colors[num - 1]--;
// delete the A[i];
colors[i] = 0;
}
}
}
int index = len - 1;
for (int i = k - 1; i >= 0; i--) {
int cnt = -colors[i];
// Empty number.
if (cnt == 0) {
continue;
}
while (cnt > 0) {
colors[index--] = i + 1;
cnt--;
}
}
}
}