LeetCode 75. Sort Colors(3色ソート→K色ソート)

3081 ワード
LeetCode
タイトルの説明:
    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.
分析:題意:赤、白、青の3色の物体をn個与え、それらを赤、白、青の色で並べ替える.整数配列では,赤,白,青の3色を0,1,2でそれぞれ表す.ソート関数は使用できません.考え方:これは古典的な3色の並べ替え問題で、双指針法で解決することができます.ポインタred=0、white=1、blue=2を初期化します.Ⅰ. whiteredでポインタwhiteが0(赤)を指す場合は、ポインタwhiteとポインタredが指す値を交換しながら、redを1つ追加する前に赤を交換する必要があります.時間的複雑度はO(n),空間的複雑度はO(1)であった.ここでは、2つのバージョンコード(構想が全体的に一致し、2番目のバージョンがより優雅である)を示します.
コード:
#include 

using namespace std;

// T(n) = O(n)
// Accepted
class Solution {
public:
    void sortColors(vector& nums) {
        int n = nums.size();
		// Exceptional Case: 
		if(n == 0){
			return;
		}
		// red, white, blue
		int red = 0, white = 0, blue = n - 1;
		// for case: [1, 0], white < blue will cause an error!
		while(white <= blue){
			if(nums[white] == 1){
				white++;
			}
			else if(nums[white] == 0){
				if(nums[red] != 0){
					swap(nums[red], nums[white]);
				}
				red++;
				white++;
			}
			else if(nums[white] == 2){
				if(nums[blue] != 2){
					swap(nums[white], nums[blue]);
				}
				blue--;
			}
		}
    }
};

コード:
#include 

using namespace std;

// T(n) = O(n)
class Solution {
public:
    void sortColors(vector& nums) {
        int n = nums.size();
		// Exceptional Case: 
		if(n == 0){
			return;
		}
		int red = 0, blue = n - 1;
		for(int white = red; white <= blue; white++){
			while(nums[white] == 2 && white < blue){
				swap(nums[white], nums[blue--]);
			}
			while(nums[white] == 0 && white > red){
				swap(nums[red++], nums[white]);
			}
		}
	}
};

拡張:k色の物体をn個与え、k色で並べ替える.整数配列では、0、1、2、...、k−1はそれぞれk色を表す.ソート関数は使用できません.構想:この問題は3色のソートの進化バージョンで、k色のソート問題は、全体的にやはり双指針法を採用して、重複部分はもう復唱しません.現在のソートで考慮されている色範囲が[c_min,c_max]であると仮定すると、初期値はc_min = 0、c_max = k - 1.1ラウンドのソート後、2色c_min = 0、c_max=k-1は処理済み(配列の両端に交換)であり、次に[c_min+1=1,c_max-1=k-2]の範囲内の色ソートを考慮し、c_min >= c_max、サイクルを終了します.時間的複雑度はO(n＊k)であった.
コード:
#include 

using namespace std;

class Solution{
public:
	void sortColorsII(vector& nums, int k){
		int n = nums.size();
		// exceptional case: 
		if(n <= 1 || k <= 1){
			return;
		}
		int c_min = 0, c_max = k - 1;
		int left = 0, right = n - 1;
		int i = 0;
		while(c_min < c_max){
			while(i <= right){
				if(nums[i] == c_min){
					swap(nums[left++], nums[i++]);
				}								
				else if(nums[i] == c_max){
					swap(nums[i], nums[right--]);
				}
				else{
					i++;
				}
			}
			i = left;
			c_min++;
			c_max--;
		}
	}
};
10個の整数のすべての奇数の加算の和
linuxシミュレーションchmodコマンド