題目
Given an array with n objects colored red, white or blue, sort them in-place 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.
Example:
Input: [2,0,2,1,1,0]
Output: [0,0,1,1,2,2]
翻譯
給定一個數(shù)組，包含n個元素懈凹，n個元素被隨機(jī)標(biāo)記了三種顏色的一種荤西，紅色滓技，白色猪狈，藍(lán)色∥蓿現(xiàn)在原地排序括儒，使相同顏色的元素相鄰茧痒，按照紅色肮韧，白色，藍(lán)色的順序排列旺订。在這里我們分別用0惹苗，1，2耸峭。代表三種顏色桩蓉。
解題思路
通過題意可知，這個數(shù)組有其特殊性劳闹，特點就是數(shù)組只包含三種元素院究。所以首先提供一種暴力的解法。就是分別統(tǒng)計每個元素在數(shù)組中出現(xiàn)了多少次本涕。然后根據(jù)元素在數(shù)組中出現(xiàn)的次數(shù)业汰，將數(shù)組重新賦值。
代碼如下：
// 75. Sort Colors
// https://leetcode.com/problems/sort-colors/description/
//
// 計數(shù)排序的思路
// 對整個數(shù)組遍歷了兩遍菩颖，第一遍統(tǒng)計各個元素個數(shù)样漆，第二遍將數(shù)組重新賦值
// 時間復(fù)雜度: O(n)
// 空間復(fù)雜度: O(k), k為元素的取值范圍
public class Solution1 {
public void sortColors(int[] nums) {
int[] count = {0, 0, 0}; // 存放0, 1, 2三個元素的頻率
for(int i = 0 ; i < nums.length ; i ++){
assert nums[i] >= 0 && nums[i] <= 2;
count[nums[i]] ++;
}
int index = 0;
for(int i = 0 ; i < count[0] ; i ++)
nums[index++] = 0;
for(int i = 0 ; i < count[1] ; i ++)
nums[index++] = 1;
for(int i = 0 ; i < count[2] ; i ++)
nums[index++] = 2;
}
}
優(yōu)化解法
在這里我們可以采用三路快排的思想，什么是三路快排呢晦闰，三路快排就是在數(shù)組中選擇一個標(biāo)定點放祟，然后以這個標(biāo)定點為依據(jù)鳍怨，將數(shù)組分為三部分，小于標(biāo)定點的數(shù)據(jù)跪妥，等于標(biāo)定點的數(shù)據(jù)鞋喇，和大于標(biāo)定點的數(shù)據(jù)。然后在小于標(biāo)定點和大于標(biāo)定點的區(qū)域繼續(xù)采用三路快排的思想排序眉撵，就是一個遞歸調(diào)用的過程侦香。對于本題，因為只有三種元素纽疟，所以一次調(diào)用就完成了整個排序過程罐韩。我們先來看幾張圖。
在這里我們新定義兩個索引zero,two污朽。當(dāng)我們遍歷數(shù)組時散吵，將0元素放到[0...zero]區(qū)間，將為2的元素放到區(qū)間[zero..n-1]中膘壶。
由上圖可知错蝴，此時我們遍歷到第i個元素洲愤。第i個元素值為2颓芭，我們就將第i個元素的值放到two-1的位置。同時將two-1位置的元素放到i的位置柬赐。就是交換這兩個位置的元素亡问。因為找出為2的元素增加了一個，所以two要減一肛宋。而此時i是不變的州藕，因為交換過來的數(shù)據(jù)是啥仍然是未知的。同理可以分析出當(dāng)?shù)趇個元素如果是0和1要應(yīng)該怎么處理酝陈。具體情況請看代碼床玻。
// 75. Sort Colors
// https://leetcode.com/problems/sort-colors/description/
//
// 三路快速排序的思想
// 對整個數(shù)組只遍歷了一遍
// 時間復(fù)雜度: O(n)
// 空間復(fù)雜度: O(1)
public class Solution2 {
public void sortColors(int[] nums) {
// [0...zero] == 0，初始情況zero為-1沉帮，此時區(qū)間無效锈死。
//如果初始值為1,那就是說區(qū)間中第一個元素是0，
//而第一個元素未知穆壕，所以這里初始值設(shè)為-1待牵；
int zero = -1;
int two = nums.length; // [two...n-1] == 2,同理初始區(qū)間是無效區(qū)間
for(int i = 0 ; i < two ; ){
if(nums[i] == 1)
i ++;
else if (nums[i] == 2)
swap(nums, i, --two); //two先自減
else{ // nums[i] == 0
assert nums[i] == 0;
swap(nums, ++zero, i++); //zero先自增
}
}
}
private void swap(int[] nums, int i, int j){
int t = nums[i];
nums[i]= nums[j];
nums[j] = t;
}
}
更多內(nèi)容歡迎大家關(guān)注
