075_(顏色分類)Sort Colors
1 問題描述、輸入輸出與樣例
1.1 問題描述
給定一個包含紅色、白色和藍色,一共 n 個元素的數組,原地對它們進行排序,使得相同顏色的元素相鄰,並按照紅色、白色、藍色順序排列。
此題中,我們使用整數 0、 1 和 2 分別表示紅色、白色和藍色。
注意:
不能使用代碼庫中的排序函數來解決這道題。
進階:
一個直觀的解決方案是使用計數排序的兩趟掃描算法。首先,迭代計算出0、1 和 2 元素的個數,然後按照0、1、2的排序,重寫當前數組。
你能想出一個僅使用常數空間的一趟掃描算法嗎?
1.2 輸入與輸出
輸入:
vector
& nums: 輸入的顏色數組
輸出:
void:原地修改
1.3 樣例
1.3.1 樣例1
輸入: [2,0,2,1,1,0]
輸出: [0,0,1,1,2,2]
2 思路描述與代碼
2.1 思路描述(一遍掃描法)
i, j, k分別指向最後的0, 1, 2位置
一趟掃描元素 x :
if(x == 0) i, j, k 位置先後置位相應的元素並位置加1
else if(x == 1) j, k 位置先後置為相應的元素並位置都加1
else k 位置置為相應的元素並位置都加1
比如輸入[2,0,2,1,1,0]
i, j, k初始化為-1
x = 2, 下標位置0置2,i = -1, j = -1, k = 0, 此時數組為[2,0,2,1,1,0]
x = 0, 下標位置1置2,下標位置0置0, i = 0, j = 0, k = 1, 此時數組為[0,2,2,1,1,0]
x = 2, 下標位置2置2,i = 0, j = 0, k = 2, 此時數組為[0,2,2,1,1,0]
x = 1, 下標位置3置2,下標位置1置1, i = 0, j = 1, k = 3, 此時數組為[0,1,2,2,1,0]
x = 1, 下標位置4置2,下標位置2置1, i = 0, j = 2, k = 4, 此時數組為[0,1,1,2,2,0]
x = 0, 下標位置5置2,下標位置3置1, 下標位置1置0, i = 1, j = 3, k = 5, 此時數組為[0,0,1,1,2,2]
2.2 代碼
<code>void sortColors(vector<int>& nums) {
int numsSize = nums.size();
int i = -1, j = -1, k = -1;//三個指針,i, j, k分別指向最後的0, 1, 2
//printf("%d %d\n", nums[0], nums[1]);
for(int l=0; l<numssize> if(0 == nums[l]){
nums[++k] = 2;
nums[++j] = 1;
nums[++i] = 0;
//printf("%d %d\n", nums[0], nums[1]);
}
else if(1 == nums[l]){
nums[++k] = 2;
nums[++j] = 1;
}
else
nums[++k] = 2;
}
}/<numssize>/<code>
代碼截圖
3 思考與拓展
3.1 思考
本題使用下標記錄三種顏色的最後一個位置,可以做到一遍掃描即原地修改。
3.1.1 其他方法
3.1.1.1 兩遍掃描
先掃描一遍,記錄0、1、2的個數
然後根據個數置0、1、2
3.1.2 複雜度分析
<table><thead>3.1.3 難點分析
i, j, k的更新規則
3.2 拓展
無。
閱讀更多 程序員喬戈裡 的文章