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.

分析：

题目本身是不允许用这种2-pass的counting sort的，但是其实这个算法真的很好，特别是k不大的时候。

counting sort本身放在后面搞。

解法：

class Solution{
public:
    /**
     * @param colors: A list of integer
     * @param k: An integer
     * @return: nothing
     */    
    void sortColors2(vector<int> &colors, int k) {
        // write your code here
        int n = colors.size();
        if (n == 0 || n < k) {
            return;
        }
        vector<int> lookUp(k, 0);
        for (int i = 0; i < n; i++) {
            lookUp[colors[i] - 1]++;
        }
        int j = 0;
        for (int i = 0; i < k; i++) {
            while (lookUp[i] != 0) {
                colors[j] = i + 1;
                lookUp[i]--;
                j++;
            }
        }
        return;
    }
};