題目連結：https://leetcode-cn.com/problems/sort-colors/
題目描述
給定一個包含紅色、白色和藍色，一共 n 個元素的數組，原地對它們進行排序，使得相同顔色的元素相鄰，并按照紅色、白色、藍色順序排列。
此題中，我們使用整數 0、 1 和 2 分别表示紅色、白色和藍色。
注意:
不能使用代碼庫中的排序函數來解決這道題。
示例:
輸入: [2,0,2,1,1,0]
輸出: [0,0,1,1,2,2]
進階：
-
一個直覺的解決方案是使用計數排序的兩趟掃描算法。
首先，疊代計算出0、1 和 2 元素的個數，然後按照0、1、2的排序，重寫目前數組。
- 你能想出一個僅使用常數空間的一趟掃描算法嗎？
思路
本問題被稱為 荷蘭國旗問題 ，最初由 Edsger W. Dijkstra提出。 其主要思想是給每個數字設定一種顔色，并按照荷蘭國旗顔色的順序進行調整。
我們用三個指針（p0, p2 和curr）來分别追蹤0的最右邊界，2的最左邊界和目前考慮的元素。
本解法的思路是沿着數組移動
curr
指針，若
nums[curr] = 0
，則将其與
nums[p0]
互換；若
nums[curr] = 2
，則與
nums[p2]
互換。
算法
- 初始化0的最右邊界：
p0 = 0
nums[idx < p0] = 0
- 初始化2的最左邊界 ：
p2 = n - 1
nums[idx > p2] = 2
- 初始化目前考慮的元素序号 ：
curr = 0
- While
curr <= p2
- 若
nums[curr] = 0
curr
p0
- 若
nums[curr] = 2
curr
p2
p2
- 若
nums[curr] = 1
curr
- 若
代碼
1
（1）疊代計算出0、1 和 2 元素的個數
（2）分别按照0、1、2的排序和個數，重寫目前數組。
時間複雜度O（N）
空間複雜度O（1）
class Solution {
public:
// 兩遍掃描 時間複雜度O(n) 空間複雜度O(1)
void sortColors(vector<int>& nums) {
int cnt[3] = {0};
for(auto n:nums){
cnt[n] += 1;
}
fill(nums.begin(), nums.begin() + cnt[0], 0);
fill(nums.begin() + cnt[0], nums.begin() + cnt[0]+cnt[1], 1);
fill(nums.begin() + cnt[0] + cnt[1], nums.end(), 2);
}
};
2
時間複雜度O（N）
空間複雜度O（1）
class Solution {
public:
// 荷蘭國旗問題
// 時間複雜度O(n) 空間複雜度O(1)
void sortColors(vector<int>& nums) {
if (nums.size() <= 1) return;
// 對于所有 idx < p0 : nums[idx < p0] = 0
// 對于所有 idx > p2 : nums[idx > p2] = 2
// curr 是目前考慮元素的下标
int p0 = 0, p2 = nums.size() -1; // p0表示0的最右邊界
int cur = 0; // p2表示2的最左邊界
while (cur <= p2){
if(nums[cur] == 0){
swap(nums[cur++],nums[p0++]);
}else if(nums[cur] == 2){
swap(nums[cur], nums[p2--]);
} else
++cur;
}
}
};