LeetCode Sort Colorsブロック処理アルゴリズムと最適化counting sortアルゴリズム

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?
科学の思惟:この問題は点があります
QuikSort思想、
しかし、ウィンドウを分けてデータを処理するという考え方は、O(∩∩)O~
1 redウィンドウ2 whiteウィンドウ3 blueウィンドウ4未処理ウィンドウ
アルゴリズム1:以下は3つの指標に分けて、それぞれの色球の末位を指しています.このアルゴリズムの利点は、成分4個、5個の色ブロックを簡単に修正できるアルゴリズムです.もちろん、色ブロックが増え続ける場合は、counting sortアルゴリズムを使用したほうがいいです.以下にもプログラムを提供します.

class Solution {
public:
	void sortColors(int A[], int n) 
	{
		int r = 0, r_w = 0, w_b = 0;
		for (int i = 0; i < n; i++)
		{
			switch (A[i])
			{
			case 0:
				{
					swap(A[i], A[r]);
					if (r_w != 0)
					{
						swap(A[i], A[r + r_w]);
					}
					if (w_b != 0)
					{
						swap(A[i], A[r + r_w + w_b]);
						//w_b++;          ，     ++
					}
					//  ：     ，     ，      。
					r++;
				}
				break;

			case 1:
				{
					swap(A[i], A[r + r_w]);
					if (w_b != 0)
					{
						swap(A[i], A[r + r_w + w_b]);
					}

					//  ：     ，     ，      。
					r_w++;
				}
				break;

			case 2:
				w_b++;
			}
		}
	}
};

アルゴリズム2:3つのブロックの特性を利用して、前のブロック、後のブロック、中間のブロックに分けて、このようにもっと処理しやすくて、プログラムも簡潔です.

class Solution {
public:
	void sortColors(int A[], int n) 
	{
		int r = 0, w = 0, b = n-1;
		for (int w = 0; w <= b; )
		{
			switch (A[w])
			{
			case 0:
				swap(A[r++], A[w++]);
				break;

			case 1:
				w++;
				break;

			case 2:
				swap(A[w], A[b--]);
			}
		}
	}
};

アルゴリズム3:Counting Sortアルゴリズム、これは汎用的なアルゴリズムで、とてもよく使われています.しかし、余分な空間O(n)を使うには、長い間考えていたので、余分な空間を使わないわけにはいかないような気がしますが、少し最適化することができます.アルゴリズム4はプログラムを与えます.

void sortColors5(int A[], int n) 
	{
		int countArray[NUM_OF_COLORS+1] = {0};

		for (int i = 0; i < n; i++)
		{
			countArray[A[i]+1]++;
		}
		
		for (int i = 2; i <= NUM_OF_COLORS; i++)
		{
			countArray[i] += countArray[i-1];
		}

		vector<int> B(A, A+n);

		for (int i = 0; i < n; i++)
		{
			B[countArray[A[i]]++] = A[i];
		}

		for (int i = 0; i < n; i++)
		{
			A[i] = B[i];
		}
	}

アルゴリズム4:counting sortを最適化し、キーワードをm(本題のキーワードは3)とするのは一般的に数列nよりも長さが小さく、余分な空間O(m)を使用すれば、多くの空間を節約することができる.次の手順で処理すればできます.

const static int NUM_OF_COLORS = 3;
	void sortColors4(int A[], int n) 
	{
		int countArray[NUM_OF_COLORS+1] = {0};

		for (int i = 0; i < n; i++)
		{
			countArray[A[i]+1]++;
		}
		
		for (int i = 2; i <= NUM_OF_COLORS; i++)
		{
			countArray[i] += countArray[i-1];
		}

		vector<int> fixedCount(countArray, countArray+NUM_OF_COLORS+1);

		int j = 0;
		for (int i = 0; i < n;)
		{
			if (A[i] != j)	swap(A[i], A[countArray[A[i]]++]);
			else 
			{
				countArray[j]++;
				i++;
			}
			while (i<n && j<=NUM_OF_COLORS && i == fixedCount[j+1])
			{
				j++;
				i = countArray[j];
			}
		}
	}

//2014-2-11 update
	void sortColors(int A[], int n) 
	{
		int red = 0, white = 0, blue = n-1;
		while (white<=blue)
		{
			if (A[white] == 0) swap(A[red++], A[white++]);
			else if (A[white] == 1) white++;
			else swap(A[white], A[blue--]);
		}
	}