Sort Colors II

Question

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.

Analysis

简单的办法可以利用two pass, 相当于counting sort,计数每个color的个数,再依次填入到原来的array中;这种方法空间复杂度为 O(k), 时间复杂度为 O(n)。
第二种则是利用两个指针的方法,设定pl和pr,左右两个指针,初始位置分别为数组两端,pl = 0, pr = colors.length - 1. 同时,由于题目限制条件,已知min和max,因此可以据此作为比较,来决定如何移动pl,pr两个指针。不断对满足min和max条件的colors进行swap,就可以在in-place的条件下,做到sorting colors,这种算法的空间复杂度为O(1), 而时间复杂度:这种方法的时间复杂度为O(n^2): T(n) = T(n - 2) + n。

Solution

public class Solution {
/**
* Method I: O(k) space, O(n) time; two-pass algorithm, counting sort
* @param colors: A list of integer
* @param k: An integer
* @return: nothing
*/
public void sortColors2TwoPass(int[] colors, int k) {
int[] count = new int[k];
for (int color : colors) {
count[color-1]++;
}
int index = 0;
for (int i = 0; i < k; i++) {
while (count[i]>0) {
colors[index++] = i+1;
count[i]--;
}
}
}
/**
* Method II:
* Each time sort the array into three parts:
* [all min] [all unsorted others] [all max],
* then update min and max and sort the [all unsorted others]
* with the same method.
*
* @param colors: A list of integer
* @param k: An integer
* @return: nothing
*/
public void sortColors2(int[] colors, int k) {
int pl = 0;
int pr = colors.length - 1;
int i = 0;
int min = 1, max = k;
while (min < max) {
while (i <= pr) {
if (colors[i] == min) {
swap(colors, pl, i);
i++;
pl++;
} else if (colors[i] == max) {
swap(colors, pr, i);
pr--;
} else {
i++;
}
// printArray(colors);
}
i = pl;
min++;
max--;
}
}
private void swap(int[] colors, int i, int j) {
int temp = colors[i];
colors[i] = colors[j];
colors[j] = temp;
}
public static void main(String[] args) {
Solution s = new Solution();
int[] colors = new int[]{2, 5, 3, 4, 2, 2, 1};
int k = 5;
s.sortColors2(colors, k);
}
private static void printArray(int[] a) {
for (int i = 0; i < a.length; i++) {
System.out.print(a[i] + " ");
}
System.out.print("\n");
}
}

Reference: