[Leetcode] Sort Colors (C++)

浏览数：22 / 时间：2015年06月08日

题目：

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.

click to show follow up.

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?

Tag:

Array, Two Pointers, Sort

体会：

这个题是看了别人的做法才后知后觉的。这个题可以说是quicksort里面的那个partition的又一个变体：partition成多段。原来的partition是只分成两段，x <= pivot 和 x > pivot。

而这道题是要求分成三段，假设我们在某个中间过程，我们正要来检查A[p] 上的元素，此时的A应该是这样子的：

　　　　[0,0,..0,1,1,..1,2,2,..2, p, unsorted part]

　　　　　　　 i　　　 j p-1

我们需要有两个指针，一个指针指着0部分的最后一位的index, 一个指着1部分的最后一位的index, 2部分的最后一位我们可以免费获得，即p-1。然后我们就来看A[p]，如果A[p]是2，什么也不做就可以继续维持原先的循环不变式；如果A[p]是1的话，那么1部分的size会变大一位，所以要j = j + 1，然后把A[j]置成1，把A[p]置成2；类似地，如果是A[p] = 0，那么0部分要变大，i = i+1, A[i] = 0, 1部分跟着顺延，j = j+1, A[j] = 1, 最后A[p]=2。

在原来的partition算法中本来是应该指针变大了以后进行“交换”操作的，而这道题不用交换可以直接赋值成0，1，或者2,是因为我们知道要赋的值。举个例子

partition中：

　　[0, 6, 5, 10, 12, 13, p, .... pivot=9]

当检查到p位，如果p<=pivot，那么是i = i +1, A[i] <-> A[p]， (即A[i] 和A[p]进行交换）。

但是这道题，我们知道如果是0部分的i = i + 1, 那么A[i] 一定是要变成0， 1部分扩大的话，j = j+1, A[j] 一定是要变成1，所以可以直接赋值，而不用交换。

啊啊，我说的太啰嗦了，完全是为了给自己做个笔记，大家不要拍我啊。。。

 1 class Solution {
 2 public:
 3     void sortColors(int A[], int n) {
 4         int i = -1;
 5         int j = -1;
 6         for (int p = 0; p < n; p++) {
 7             if (A[p] == 2) {
 8                 // do nothing but moving the index of k
 9             } else if (A[p] == 1) {
10                 // 
11                 A[p] = 2;
12                 A[++j] = 1;
13             } else {
14                 A[p] = 2;
15                 A[++j] = 1;
16                 A[++i] = 0;
17             }
18         }
19     }
20 };