leetcode_75_Sort Colors

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.


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?




方法一：解題思路
e0代表endOfZero； e1代表endOfOne；curId代表當前遍歷的值
從後往前遍歷，循環一遍
當A[curId]=1,交換A[curId]和A[e0]，即將1都交換到最後一個0的位置。成功後e0--，最後一個0的位置向前移了一位
當A[curId]=2,交換A[curId]和A[e0]，再交換A[e1]和A[e0]，即將2都交換到最後一個0的位置，再將2交換到最後一個1的位置。成功後e0--和e1--，最後一個0和1的位置向前移了一位

//vs2012測試代碼
#include

using namespace std;

#define N 7

class Solution {
public:
    void sortColors(int A[], int n) 
	{
        int e0=n-1 , e1=n-1;
		for(int curId=n-1; curId>=0; curId--)
		{
			if( A[curId] == 1)
			{
				swap( A[curId],A[e0] );
				e0--;
			}
			if( A[curId] == 2)
			{
				swap( A[curId],A[e0] );
				swap( A[e0],A[e1] );
				e0--;
				e1--;
			}
		}
		for(int i=0; i
//方法一：自測Accepted
//reverse travel the array 
//e0代表endOfZero； e1代表endOfOne
//從後往前遍歷，循環一遍
//當A[curId]=1,交換A[curId]和A[e0]，即將1都交換到最後一個0的位置。成功後e0--，最後一個0的位置向前移了一位
//當A[curId]=2,交換A[curId]和A[e0]，再交換A[e1]和A[e0]，即將2都交換到最後一個0的位置，再將2交換到最後一個1的位置。成功後e0--和e1--，最後一個0和1的位置向前移了一位

class Solution {
public:
    void sortColors(int A[], int n) 
	{
        int e0=n-1 , e1=n-1;
		for(int curId=n-1; curId>=0; curId--)
		{
			if( A[curId] == 1)
			{
				swap( A[curId],A[e0] );
				e0--;
			}
			if( A[curId] == 2)
			{
				swap( A[curId],A[e0] );
				swap( A[e0],A[e1] );
				e0--;
				e1--;
			}
		}
		for(int i=0; i
//方法二：記錄各自次數，在原數組重新賦值0,1,2
class Solution {
public:
    void sortColors(int A[], int n) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int r = 0, w = 0, b = 0;
        for (int i = 0; i < n; i++) {
            r += A[i] == 0;
            w += A[i] == 1;
            b += A[i] == 2;
        }
        for (int i = 0; i < n; i++) {
            A[i] = i < r ? 0 : i < r + w ? 1 : 2;
        }        
    }
};



//方法三：這都能通過，應該是OJ的bug
class Solution {
public:
    void sortColors(int A[], int n) 
	{
        sort(A,A+n);
    }
};