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

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

A rather straight forward solution is a two-pass algorithm using counting sort. That will cost O(k) extra memory.

Can you do it without using extra memory?

Analysis:

Sort: O(nlogn), quick or merge.

O(n): use the array itself as space to store counts. We use A[k-1] to store the count of color k. We use negtive number to store count, in order to be distnct with the color value. This method ASSUMES that every color between 1 and k will appear.

At position i, we check the value of A[A[i]-1], if it is a positive number, i.e., not counted yet, we then put A[A[i]-1] to A[i], and set A[A[i]-1] as -1 to indicate that there is one of this color.

If A[A[i]-1] is a negtive or zero value, we then simply decrease it by one and set A[i] as 0 to indicate that this position is couted already.

At position i, we repeat this procedure until A[i] becomes 0 or negtive, we then move to i+1.

At counting, we draw colors into array.

Solution:

 1 class Solution { 2     /** 3      * @param colors: A list of integer 4      * @param k: An integer 5      * @return: nothing 6      */ 7     public void sortColors2(int[] colors, int k) { 8         //The method assumes that every color much appear in the array. 9         int len = colors.length;10         if (len<k) return;11 12         //count the number of each color.13         for (int i=0;i<len;i++){14             while (colors[i]>0){15                 int key = colors[i]-1;16                 if (colors[key]<=0){17                     colors[key]--;18                     colors[i]=0;19                 } else {20                     colors[i] = colors[key];21                     colors[key] = -1;22                 }23             }24         }25 26         //draw colors.27         int index = len-1;28         int cInd = k-1;29         while (cInd>=0){30             int num = Math.abs(colors[cInd]);31             for (int i=0;i<num;i++){32                 colors[index]=cInd+1;33                 index--;34             }35             cInd--;36         }37     }38 }