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.

Example

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

Solution

方法一： 可以借助一个O(k)的数组bucket，然后扫一遍原来的数组，统计每一种颜色有多少个存放在数组bucket里面，然后题目要求把颜色排序，其实就是再把b里面的统计重新输出到原来的数组就好了。

方法二： 这道题原数组还要重复利用作为bucket数组!!! 首先for循环遍历一遍原来的数组，如果扫到a[i]，首先检查a[a[i]]是否为正数，如果是把a[a[i]]移动a[i]存放起来，然后把a[a[i]]记为-1(表示该位置是一个计数器，计1)。 如果a[a[i]]是负数，那么说明这一个地方曾经已经计数了，那么把a[a[i]]计数减一，并把color[i] 设置为0 （表示此处已经计算过），当当前的i的值小于等于0了，在通过外循环遍历到下一个i，然后重复向下遍历下一个数，这样遍历原数组所有的元素过后，数组a里面实际上存储的每种颜色的计数，然后我们倒着再输出每种颜色就可以得到我们排序后的数组。

例子(按以上步骤运算)：

3 2 2 1 4

2 2 -1 1 4

2 -1 -1 1 4

0 -2 -1 1 4

-1 -2 -1 0 4

-1 -2 -1 -1 0

花了4个小时终于顿悟理解了：

首先遍历第当前的i , 如果当前的i的位置的值大于0，则置换并且把新位置设置为－1， 如果a[a[i]] 是负数则累加，并且设置当前i 为0， 反复置换直到当前的i <=0

when get the colors array , don't do the forward loop, do reverse loop in case of override values,

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

class Solution:
    """
    @param colors: A list of integer
    @param k: An integer
    @return: nothing
    """
    def sortColors2(self, colors, k):
        count = [0] * k
        for color in colors:
            count[color - 1] += 1

        index = 0

        for i in range(k):
            while count[i] > 0:
                colors[index] = i + 1
                index += 1
                count[i] -= 1