Lintcode: Sort Colors II 解题报告

柔光的暖阳◎ 2022-04-22 15:26 228阅读 0赞

# [Sort Colors II ][Sort Colors II] #

原题链接： [http://lintcode.com/zh-cn/problem/sort-colors-ii/\#][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.

**注意**

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?

![188066593-close-up-of-multicolor-balls-of-yarn-gettyimages.jpg_v_1_c_IWSAsset_k_2_d_LuZR8KiKYRZik1AAO_2Frba9undeOMftUO1x0ZqH4DzMPPkI0qL7OtEu0J9iYOWhoO][]

## SOLUTION 1: ##

使用快排，时间复杂度是O(nlogn),空间复杂度是O(Log(N))

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 /**
     2      * @param colors: A list of integer
     3      * @param k: An integer
     4      * @return: nothing
     5      */
     6     /*
     7     Solution 1: Using the quick sort.
     8     */ 
     9     public void sortKColors1(int[] colors, int k) {
    10         // write your code here
    11         if (colors == null) {
    12             return;
    13         }
    14         
    15         quickSort(colors, 0, colors.length - 1);
    16     }
    17     
    18     public void quickSort(int[] colors, int left, int right) {
    19         if (left >= right) {
    20             return;
    21         }
    22         
    23         int pivot = colors[right];
    24         
    25         int pos = partition(colors, left, right, pivot);
    26         
    27         quickSort(colors, left, pos - 1);
    28         quickSort(colors, pos + 1, right);
    29     }
    30     
    31     public int partition(int[] colors, int left, int right, int pivot) {
    32         int leftPoint = left - 1;
    33         int rightPoint = right;
    34         
    35         while (true) {
    36             while (colors[++leftPoint] < pivot);
    37             
    38             while (leftPoint < rightPoint && colors[--rightPoint] > pivot);
    39             
    40             if (leftPoint >= rightPoint) {
    41                 break;
    42             }
    43             
    44             swap(colors, leftPoint, rightPoint);
    45         }
    46         
    47         swap(colors, leftPoint, right);
    48         return leftPoint;
    49     }
    50     
    51     public void swap(int[] colors, int left, int right) {
    52         int tmp = colors[left];
    53         colors[left] = colors[right];
    54         colors[right] = tmp;
    55     }

## SOLUTION 2: ##

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

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

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         }

### GITHUB: ###

[https://github.com/yuzhangcmu/LeetCode\_algorithm/blob/master/lintcode/array/SortKColors.java][https_github.com_yuzhangcmu_LeetCode_algorithm_blob_master_lintcode_array_SortKColors.java]

[Sort Colors II]: http://lintcode.com/zh-cn/problem/sort-colors-ii/
[188066593-close-up-of-multicolor-balls-of-yarn-gettyimages.jpg_v_1_c_IWSAsset_k_2_d_LuZR8KiKYRZik1AAO_2Frba9undeOMftUO1x0ZqH4DzMPPkI0qL7OtEu0J9iYOWhoO]: http://cache3.asset-cache.net/gc/188066593-close-up-of-multicolor-balls-of-yarn-gettyimages.jpg?v=1&c=IWSAsset&k=2&d=LuZR8KiKYRZik1AAO%2Frba9undeOMftUO1x0ZqH4DzMPPkI0qL7OtEu0J9iYOWhoO
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20220327/d26b994e5e6f4281afb4e11708c3a9b1.png
[https_github.com_yuzhangcmu_LeetCode_algorithm_blob_master_lintcode_array_SortKColors.java]: https://github.com/yuzhangcmu/LeetCode_algorithm/blob/master/lintcode/array/SortKColors.java