It is a very old leetcode problem. Because I want to find out which problem in the leetcode is unfinished yesterday, I reuploaded all my code to leetcode. Then I found out that I have not finished this problem.
This problem requires only one pass.
The main idea of the solution is to guess that there is a sequence of “111111”in the array. Assume the head location of the sequence is firstOne, the rear of the sequence is lastOne. We need put all the “0” before the firstOne, and put all the “2” after the lastOne.
We first guess all the element s in the array is 1. The we check the location one by one.
when the checked element is zero,
(1) check location larger than firstOne.
This means that there must be an 1111 sequence before. We can swap the element the firstOne points to with the element now check(which is 0). It means we insert the 0 element before the firstOne. And the firstOne plus one.(Because the header of sequence 111111 is move behind for one location.)
(2) check location equal to firstOne.
This means that the header of “111111” we guess is not correct. The header of “111111”is zero, so we need to guess the location behind this header and check this location. (nowCheck++ and firstOne++)
(3) check location before firstOne.
Impossible, because we only move firstOne backwards after we check the location. Thus, firstOne must smaller than the check location or equal as the check location.
when the checked element is 1,
just need to check the location behind. (The main idea of the solution is put all “0” before the guess sequence “1111”, put “2” after the guessing sequence.)
when the checked element is 2,
we need to swap this element with the last One of guessing sequence “1111”. lastOne location minus one. (Because we put an “2” behind the guessing sequence”111111″ )
/*
只扫描一遍的思路如下：
我们需要维持3段有序的在数组里面
我们可以假设数组里面有一段111111，不过不知道数量是多少，可能没有，我们用两个变量去标识这段东西的头和尾部
然后把扫到的所有0都摆在这段的前面，也就是头的前面，扫到的2都摆在这段的后面。
当扫的指针遇上这段的尾部的尾部就扫描完了，因为尾部后面必然都是2
*/
class Solution {
public:
void sortColors(int A[], int n) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
int nowCheck=0;
int firstOne=0;//初期假设整条序列都是1，那么第一个就是位置0，最后一个就是位置n-1
int lastOne=n-1;
while(nowCheck<=lastOne)
{
if (A[nowCheck]==0)
{
//当前扫描位置在1111段的头之后，前面必定有1的值
if (nowCheck>firstOne)
{
//当前扫描位置大于1字符段的开头，证明前面必然有1，交换他们的值，当前扫描位置的值就是1，在下一次判断时候指针就会往后挪
swap(A[nowCheck],A[firstOne]);
firstOne++;//因为当前扫到的是0，所以和1字符段开头的第一个元素交换，1字符段的头元素就要往后挪一位了，相当于前面插了一个0
}
else if (nowCheck==firstOne)
{
/*因为firstOne实际上是猜测的1段的开头，当检测的位置和猜测的1段头相同的时候
并且检测到0的时候，之前的必然都是0，所以这个位置不用动。检测位置挪去下一位，同样猜测的1段开头要往后挪
*/
nowCheck++;
firstOne++;
}
//不可能nowCheck在firstOne之前，因为猜测的1段能够往后移动必须要之前的位置都被检测过，一开始检测位置和猜测1段开始的位置两个的位置重合
//firstone只有在nowCheck之前才会往后移动，而两者位置相同的时候都是同时往后移动
}
else if (A[nowCheck]==1)
{
//检测到1的时候，不需要移动，因为我们只需要把0摆在1的前面，2摆在1的后面就可以了
nowCheck++;
}
else if (A[nowCheck]==2)
{
//因为nowcheck必然小于lastOne，否则就可以结束了,当遇到2的时候直接交换猜测1段的最后一个位置
swap(A[nowCheck],A[lastOne]);
lastOne--;
}
}
}
};
Test Result:
small data:
large data:
Poly-Thinking 