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.NoteYou are not suppose to use the library's sort function for this PRoblem.ExampleGIven colors=[3, 2, 2, 1, 4], k=4, your code should sort colors in-place to [1, 2, 2, 3, 4]. ChallengeA 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?

先寫了個O(kN)時間復雜度，O（1）空間復雜度的， 這個算法適合顏色數比較少的情況（k is constant）

 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         // write your code here 9         if (colors==null || colors.length==0 || k<=1) return;10         int l=0, r=colors.length-1;11         int pivot = r;12             while (true) {13                 while (l<r && colors[l]<colors[pivot]) {14                     r--;15                 }16                 while (l<r && colors[l]==cnt) {17                     l++;18                 }19                 if (l == r) break;20                 swap(colors, l, r);21             }22             l++;23             r = colors.length-1;24             if (l == r) break;25     }26     27     public void swap(int[] colors, int l, int r) {28         int temp = colors[l];29         colors[l] = colors[r];30         colors[r] = temp;31     }32 }

K->N的話，上面時間復雜度就大了，所以干脆用Quick Sort

 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         // write your code here 9         if (colors==null || colors.length==0 || k<=1) return;10         quickSort(colors, 0, colors.length-1);11     }12     13     public void quickSort(int[] colors, int l, int r) {14         if (l >= r) return;15         int pivot = r;16         int pos = partition(colors, l, r, pivot);17         quickSort(colors, l, pos-1);18         quickSort(colors, pos+1, r);19     }20     21     public int partition(int[] colors, int start, int end, int pivot) {22         int l=start, r=end;23         while (true) {24             while (l<r && colors[l]<colors[pivot]) {25                 l++;26             }27             while (l<r && colors[r]>=colors[pivot]) {28                 r--;29             }30             if (l == r) break;31             swap(colors, l, r);32         }33         swap(colors, l, end);34         return l;35     }36     37     public void swap(int[] colors, int l, int r) {38         int temp = colors[l];39         colors[l] = colors[r];40         colors[r] = temp;41     }42 }

網上有人給出了O（N）的解法，沒懂

inplace，并且O(N)時間復雜度的算法。

我們可以使用類似桶排序的思想，對所有的數進行計數。

1. 從左掃描到右邊，遇到一個數字，先找到對應的bucket.比如

3 2 2 1 4

第一個3對應的bucket是index = 2 (bucket從0開始計算）

2. Bucket 如果有數字，則把這個數字移動到i的position(就是存放起來），然后把bucket記為-1(表示該位置是一個計數器，計1）。

3. Bucket 存的是負數，表示這個bucket已經是計數器，直接減1. 并把color[i] 設置為0 （表示此處已經計算過）

4. Bucket 存的是0，與3一樣處理，將bucket設置為-1， 并把color[i] 設置為0 （表示此處已經計算過）

5. 回到position i，再判斷此處是否為0（只要不是為0，就一直重復2-4的步驟）。

6.完成1-5的步驟后，從尾部到頭部將數組置結果。（從尾至頭是為了避免開頭的計數器被覆蓋）

例子(按以上步驟運算)：

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

 1 // Solution 2: inplace, O(n)  2     public void sortKColors(int[] colors, int k) { 3         // write your code here 4         if (colors == null) { 5             return; 6         } 7          8         int len = colors.length; 9         for (int i = 0; i < len; i++) {10             // Means need to deal with A[i]11             while (colors[i] > 0) {12                 int num = colors[i];13                 if (colors[num - 1] > 0) {    14                     // 1. There is a number in the bucket, 15                     // Store the number in the bucket in position i;16                     colors[i] = colors[num - 1];17                     colors[num - 1] = -1;18                 } else if (colors[num - 1] <= 0) {19                     // 2. Bucket is using or the bucket is empty.20                     colors[num - 1]--;21                     // delete the A[i];22                     colors[i] = 0;23                 }24             }25         }26         27         int index = len - 1;28         for (int i = k - 1; i >= 0; i--) {29             int cnt = -colors[i];30             31             // Empty number.32             if (cnt == 0) {33                 continue;34             }35                                 36             while (cnt > 0) {37                 colors[index--] = i + 1;38                 cnt--;39             }40         }