简单的办法可以利用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。
Copy 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" );
}
}