Sort Colors II

LintCode Sort Colors II

Question

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.

Analysis

简单的办法可以利用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。

Solution

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");
    }
}

Reference:

http://blog.welkinlan.com/2015/08/25/sort-colors-i-ii-leetcode-lintcode-java/ http://www.cnblogs.com/yuzhangcmu/p/4177326.html http://blog.csdn.net/nicaishibiantai/article/details/43306431