LeetCode Online Judge 题目C# 练习 - Sort Color

Given an array with n objects colored red, white or blue, sort them so that objects of the same color are adjacent, with the colors in the order red, white and blue.

Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.

Note:

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

Follow up:

A rather straight forward solution is a two-pass algorithm using counting sort.

First, iterate the array counting number of 0's, 1's, and 2's, then overwrite array with total number of 0's, then 1's and followed by 2's.

Could you come up with an one-pass algorithm using only constant space?

 1         public static void SortColor(int[] A)
 2         {
 3             int[] temp = new int[3];
 4             for (int i = 0; i < A.Length; i++)
 5             {
 6                 if (A[i] == 0)
 7                     temp[0]++;
 8                 else if (A[i] == 1)
 9                     temp[1]++;
10                 else if (A[i] == 2)
11                     temp[2]++;
12             }
13 
14             for (int i = 0; i < A.Length; i++)
15             {
16                 if (temp[0] > 0)
17                 {
18                     A[i] = 0;
19                     temp[0]--;
20                 }
21                 else if (temp[1] > 0)
22                 {
23                     A[i] = 1;
24                     temp[1]--;
25                 }
26                 else if (temp[2] > 0)
27                 {
28                     A[i] = 2;
29                     temp[2]--;
30                 }
31             }
32         }

代码分析：

　　Count Sort。撸两遍，第一遍先记录0，1， 2出现的次数，第二遍改。题目的follow up要求只撸一边。看下面的代码。

 1         public static void SortColorOnePass(int[] A)
 2         {
 3             int n = A.Length;
 4             int l = 0;
 5             int k = 0;
 6             int r = n - 1;
 7 
 8             while (k <= r)
 9             {
10                 if (A[k] == 0)
11                     SortColorSwap(A, l++, k++);
12                 else if (A[k] == 2)
13                     SortColorSwap(A, k, r--);
14                 else
15                     k++;
16             }
17         }
18 
19         public static void SortColorSwap(int[] A, int i, int j)
20         {
21             int temp = A[i];
22             A[i] = A[j];
23             A[j] = temp;
24         }

代码分析：

　　只撸一遍的做法，做三个指针， l， r， k， k顺序往前走，碰到0， Swap(A[k++], A[l++]), 碰到1不管，碰到2， Swap（A[k], A[r--]), 因为前面的数肯定不会是2， 所有k可以++，但是后面的数有可能是0, 交换后，还有跟前面交换，所以k不能++。

　　我也有个follow up question. 如果4种或以上的颜色，还能不能一撸搞定呢？我没想到。。。