75. 颜色分类
3 min
题目
解法：三指针
思路
第一段：使用三指针（low、mid、high）一次遍历完成排序，是经典的荷兰国旗问题解法。
第二段：算法维护四个区间的不变性：[0,low-1]全为0，[low,mid-1]全为1，[mid,high]未处理，[high+1,n-1]全为2。当mid遇到0时与low交换并前移双指针，确保0归位；遇到1时直接跳过；遇到2时与high交换并后移high指针，但不前移mid，因为交换后的元素可能仍是0或1需要再次处理。这种策略保证了每个元素最多被交换两次，且不会错过任何可能的正确位置。
第三段：
- Step 1: 初始化low=0, mid=0, high=n-1
- Step 2: 当mid<=high时循环处理
- Step 3: 若nums[mid]==0，交换nums[low]和nums[mid]，low和mid都自增
- Step 4: 若nums[mid]==1，仅mid自增
- Step 5: 若nums[mid]==2，交换nums[mid]和nums[high]，high自减
- Step 6: 循环结束，数组排序完成
复杂度
- 时间复杂度:
- 空间复杂度:
代码
class Solution {
public:
void sortColors(vector<int>& nums) {
int low = 0;
int mid = 0;
int 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{
swap(nums[mid], nums[high]);
high--;
}
}
}
};