Leetcode | Sort Colors

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?

如提示，最簡單的就是掃描兩遍，第一遍計數，第二遍填數。

32ms

一遍的沒想清楚，看完網上的思路再重寫了一遍。我的了解是這樣：

雙指針，red 記錄已經放在正确位置的0的個數，blue記錄已經放在正确位置的2的個數。同時用i從頭掃描到blue。

1. 當碰到0時，放到a[red]這個位置上，red需要累加，i也需要累加。red累加很好了解，i累加是因為red必然<=i，

當a[i]=0時，和a[red]交換之後，要想在a[red+1...i]之間再找到0已經不可能了，因為0值都被交換到red前面了，是以要想再找到0值隻能i++。

2. 當i到達blue的位置的時候，因為a[blue+1...n-1]都是2，是以已經不用再繼續了。可以退出。

3. 注意blue這個位置還沒有填充2，是以i是可以，也必須走到blue的。

8ms