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.

分析：

解法1：O(1)space

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
        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 curr = left;
            while (curr <= right) {
                if (colors[curr] <= min) {
                    int temp = colors[left];
                    colors[left] = colors[curr];
                    colors[curr] = temp;

                    curr++;
                    left++;
                } else if (colors[curr] > min && colors[curr] < max) {
                    curr++;
                } else {
                    int temp = colors[right];
                    colors[right] = colors[curr];
                    colors[curr] = temp;

                    right--;
                }
            }
            count += 2;
            start = left;
            end = right;
        }
    }
}

解法2：O(n)time, O(k)space

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
        int[] count = new int[k];
        for (int i = 0; i < colors.length; i++) {
            count[colors[i] - 1]++;
        }
        int sum = 0;
        for (int i = 0; i < k; i++) {
            sum += count[i];
            count[i] = sum;
        }
        int index = 0;
        for (int i = 0; i < k; i++) {
            while (index < count[i] ) {
                colors[index] = i + 1;
                index++;
            }
        }
        return;
    }
}