LintCode 143 · Sort Colors II.java

	public class Solution {
	/**
	* @param colors: A list of integer
	* @param k: An integer
	* @return: nothing
	*/
	public void sortColors2(int[] colors, int k) {
	// write your code here
	if (colors == null || colors.length == 0) {
	return;
	}
	// first round, count the occurance of each color.
	int n = colors.length;
	int[] counts = new int[k + 1];
	for (int color : colors) {
	counts[color]++;
	}
	// 2nd round, fill the colors array according to the calculated occurances.
	int i = 0;
	for (int color = 1; color <= k; color++) {
	int count = counts[color];
	while (count-- > 0) {
	colors[i++] = color;
	}
	}
	return;
	}
	}

view raw LintCode 143 · Sort Colors II.java hosted with ❤ by GitHub