75. 顏色分類

給定一個包含紅色、白色和藍色、共?n?個元素的數組?nums?，原地?對它們進行排序，使得相同顏色的元素相鄰，并按照紅色、白色、藍色順序排列。

我們使用整數?0、?1?和?2?分別表示紅色、白色和藍色。

必須在不使用庫內置的 sort 函數的情況下解決這個問題。

class Solution {
public:void sortColors(vector<int>& nums) {int red =0,white = 0,blue = 0;for(int i=0;i<nums.size();i++){if(nums[i]==0)red++;else if(nums[i]==1)white++;else blue++;}for(int i=0;i<nums.size();i++){if(i<red)nums[i]=0;else if(i<white+red) nums[i]=1;else nums[i]=2;}}
};

其實排個序就行，我這是按提示寫的，時間復雜度較排序更低

如果面試，最好是用三指針法，只需一次遍歷

class Solution {
public:void sortColors(vector<int>& nums) {int low = 0, mid = 0, high = nums.size() - 1;while (mid <= high) {if (nums[mid] == 0) {swap(nums[low], nums[mid]);low++;mid++;} else if (nums[mid] == 1) {mid++;} else { // nums[mid] == 2swap(nums[mid], nums[high]);high--;}}}
};

邏輯就是用指針標記0，1，2所在位置，然后遍歷時交換即可