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.

Notice

You are not suppose to use the library's sort function for this problem.

Example

Given colors=[3, 2, 2, 1, 4], k=4, your code should sort colors in-place to [1, 2, 2, 3, 4].

Tips:

这个方法比较复杂，每次要找当时的最大颜色和最小颜色，分别加在两端，然后count + 2，接着走，直到count = k。

TimeO(k/2 *n)

Count sort走两遍也行，就是要用O(K)空间，时间是O(n)。

Code：

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 || k <= 1) {
            return;
        }
        int start = 0;
        int end = colors.length - 1;
        int count = 0;
        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 i = left;
            while (i <= right) {
                if (colors[i] == min) {
                    swap(colors, i, left);
                    left++;
                    i++;
                } else if (colors[i] == max) {
                    swap(colors, i, right);
                    right--;
                } else {
                    i++;
                }
            }
            count = count + 2;
            start = left;
            end = right;
        }
        return;
    }

    private void swap(int[] colors, int i, int pos) {
        int temp = colors[i];
        colors[i] = colors[pos];
        colors[pos] = temp;
    }
}

Count Sort:

class Solution {
    public void sortColors2(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]--;
            }
        }
    }
}