數據結構和算法 - 629，顏色分類-三指針解決－鑽石舞台

問題描述

來源：LeetCode第75題

難度：中等

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

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

示例 1：

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

輸出：[0,0,1,1,2,2]

示例 2：

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

輸出：[0,1,2]

示例 3：

輸入：nums = [0]

輸出：[0]

示例 4：

輸入：nums = [1]

輸出：[1]

提示：

n == nums.length

1 <= n <= 300

nums[i] 為 0、1 或 2

三指針解決

數組中只有3種數字0，1，2。我們只需要把0往前面移，3往後面移即可。難度不是很大，我們以示例一為例來看個視頻

再來看下代碼

//三指針publicvoidsortColors(int[]nums){//0的右邊界intleft=0;//2的左邊界intright=nums.length-1;//指向當前數字intindex=0;while(index<=right){if(nums[index]==0){//如果是0，就往前面移swap(nums,left++,index++);}elseif(nums[index]==1){index++;}elseif(nums[index]==2){//如果是2就往後面移swap(nums,right--,index);}}}//交換數組中的兩個數字privatevoidswap(int[]nums,inti,intj){inttmp=nums[i];nums[i]=nums[j];nums[j]=tmp;}