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

使用整數0、1和2分布表示紅色、白色和藍色。

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

示例1：

輸入：nums = [2,0,2,1,1,0]
輸出：[0,0,1,1,2,2]

示例2：

輸入：nums = [2,0,1]
輸出：[0,1,2]

提示：

• n == nums.length
• 1 <= n <= 300
• nums[i]?為?0、1?或?2
• 進階：你能想出一個僅使用常數空間的一趟掃描算法嗎？

本題是經典的【荷蘭國旗問題】，由計算機科學家?Edsger W. Dijkstra?首先提出。

解題思路：

方法一：單指針

兩次遍歷：在第一次遍歷中，將數組中所有的0交換到數組頭部。

? ? ? ? ? ? ? ? ? 第二次遍歷中，將數組中所有的1交換到頭部的0之后。

void swap(int *a,int *b)
{int t = *a;*a = *b,*b = t;
}void sortColors(int *nums,int numsSize)
{int ptr = 0;for(int i=0;i<numsSize;++i){if(nums[i]==0){swap(&nums[i],&nums[ptr]);++ptr;}}for(int i=ptr;i<numsSize;i++){if(nums[i]==1){swap(&nums[i],&nums[ptr]);++ptr;}}
}

?時間復雜度：O（n）,其中n是數組nums的長度。

?空間復雜度：O（1）

方法二：雙指針

使用兩個指針分別來交換0和1

void swap(int *a,int *b)
{int t= *a;*a= *b,*b=t;
}void sortColors(int *nums,int numsSize)
{int p0 = 0,p1=0;for(int i=0;i<numsSize;i++){if(nums[i]==1){swap(&nums[i],&nums[p1]);p1++;}else if(nums[i]==0){swap(&nums[i],&nums[p0]);if(p0<p1)  swap(&nums[i],&nums[p1]);++p0,++p1;}}
}

時間復雜度：O（n）,其中n是數組nums的長度

空間復雜度：O（1）

方法三：雙指針

左指針P0來交換0

右指針P2來交換2

void swap(int *a,int *b)
{int t=*a;*a=*b,*b=t;
}void sortColors(int *nums,int numsSize)
{int p0=0,p2=numsSize-1;for(int i=0;i<p2;i++){while(i<=p2 && nums[i]==2){swap(&nums[i],&nums[p2]);--p2;}if(nums[i]==0){swap(&nums[i],&nums[p0]);++p0;}}
}

時間復雜度：O（n），其中n是數組nums的長度

空間復雜度：O（1）

方法四：記錄0 1 2的個數，對其進行賦值即可。