Sort Colors II
Given an array of n objects with k different colors (numbered from 1 to k), sort them so that objects of the same color are adjacent, with the colors in the order 1, 2, ... k.
Notice: You are not suppose to use the library's sort function for this problem.
Example: Given colors=[3, 2, 2, 1, 4], k=4, your code should sort colors in-place to [1, 2, 2, 3, 4].
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 == 0) {
return;
}
int count = 0;
int start = 0;
int end = colors.length - 1;
while (count < k) {
int min = Integer.MAX_VALUE;
int max = Integer.MIN_VALUE;
for (int i = start; i <= end; i++) {
min = Math.min(min, colors[i]);
max = Math.max(max, colors[i]);
}
int left = start;
int right = end;
int i = left;
while (i <= right) {
if (colors[i] == min) {
swap(colors, i, left);
i++;
left++;
} else if (colors[i] > min && colors[i] < max) {
i++;
} else {
swap(colors, i, right);
right--;
}
}
count += 2;
start = left;
end = right;
}
}
private void swap(int[] a, int i, int j) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
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--;
}
}
}
}
Hope this helps,
Michael
