原題
給定一個包含紅色、白色和藍(lán)色，一共 n 個元素的數(shù)組，原地對它們進(jìn)行排序，使得相同顏色的元素相鄰，并按照紅色、白色、藍(lán)色順序排列。
此題中，我們使用整數(shù) 0、 1 和 2 分別表示紅色、白色和藍(lán)色。
注意:
不能使用代碼庫中的排序函數(shù)來解決這道題。
示例:
輸入: [2,0,2,1,1,0]
輸出: [0,0,1,1,2,2]
進(jìn)階：
* 一個直觀的解決方案是使用計數(shù)排序的兩趟掃描算法。
首先，迭代計算出0、1 和 2 元素的個數(shù)，然后按照0、1、2的排序，重寫當(dāng)前數(shù)組。
* 你能想出一個僅使用常數(shù)空間的一趟掃描算法嗎？
原題url：https://leetcode-cn.com/problems/sort-colors/
解題
兩趟掃描
我當(dāng)時想到的第一種想法就是排序，后來感覺沒有必要，因為只有3種元素，我完全就可以按照進(jìn)階提示中的第一條，先掃描統(tǒng)計出各元素個數(shù)，然后第二遍掃描時，直接進(jìn)行賦值。
讓我們直接來看代碼：
class Solution {
public void sortColors(int[] nums) {
// 記錄0,1,2的個數(shù)
int num0 = 0, num1 = 0, num2 = 0;
// 計算各個數(shù)字出現(xiàn)的次數(shù)
for (int i : nums) {
switch(i) {
case 0:
num0++;
break;
case 1:
num1++;
break;
case 2:
num2++;
break;
}
}
// 重新賦值
for (int i = 0; i < nums.length; i++) {
if (i < num0) {
nums[i] = 0;
} else if (i < num0 + num1) {
nums[i] = 1;
} else {
nums[i] = 2;
}
}
}
}
提交OK，執(zhí)行用時：0 ms，內(nèi)存消耗：35.2 MB。是否還可以優(yōu)化呢？
優(yōu)化
參考進(jìn)階提示中的第二條，上面的方法使用了常數(shù)空間，但一遍掃描該如何做到呢？
我其實并沒有想出來，參考了別人的解法：利用三個指針進(jìn)行一次遍歷并交換。
具體來說，就是增加一個當(dāng)前指針current（從下標(biāo)0開始）、一個指向數(shù)字0區(qū)間的末尾指針p0（從下標(biāo)0開始）、一個指向數(shù)字2區(qū)間的開始指針p2（從下標(biāo) nums.length - 1）。下標(biāo)0 到下標(biāo) p0 之間存放數(shù)字0，下標(biāo) p0 到 p2 之間存放數(shù)字1，下標(biāo) p2 到 下標(biāo) (nums.length - 1) 之間存放數(shù)字2。current 指針從下標(biāo)0開始遍歷，如果值為0，則和 p0 交換，如果值為2，則和 p2 交換。
讓我們來看看代碼：
class Solution {
public void sortColors(int[] nums) {
// 利用3個指針current、p0、p2
int current = 0, p0 = 0, p2 = nums.length - 1;
while (current <= p2) {
// 如果當(dāng)前值為1，current指針往后移動
if (nums[current] == 1) {
current++;
continue;
}
// 如果當(dāng)前值為0，則和 p0 交換，p0指針往后移動
if (nums[current] == 0) {
nums[current] = nums[p0];
nums[p0] = 0;
// 因為p0一開始和current相同
if (p0 == current) {
current++;
}
p0++;
continue;
}
// 如果當(dāng)前值為2，則和 p2 交換，p2指針往前移動
if (nums[current] == 2) {
nums[current] = nums[p2];
nums[p2] = 2;
p2--;
continue;
}
}
}
}
提交OK，執(zhí)行用時：0 ms，內(nèi)存消耗：35 MB。這結(jié)果，感覺好像沒有多少優(yōu)化，但對于我們而言，最重要的是增加了一種解題思路。
總結(jié)
以上就是這道題目我的解答過程了，不知道大家是否理解了。這道題主要在于利用指針一遍掃描得出結(jié)果，優(yōu)化解題。
有興趣的話可以訪問我的博客或者關(guān)注我的公眾號、頭條號，說不定會有意外的驚喜。
公眾號：健程之道
