75.颜色分类 (Medium)*

题目描述*

标签*

排序；

思路 & 代码*

原地不适用计数数组，类似三路快排的划分过程，我们只要指定标准值 1，把 0 和 2 交换到两侧即可。三路快排的需要递归是因为不能确定 pivot。

原地

class Solution {
public:
    void sortColors(vector<int>& nums) {
        int n = nums.size();
        int l = 0, r = n - 1;
        int pivot = 1;
        int i = l;
        while(i <= r) {
            if(nums[i] == pivot) {
                i++;
            }else if(nums[i] < pivot) {
                swap(nums[i++], nums[l++]);
            }else {
                swap(nums[i], nums[r--]);
            }
        }  
    }
};

最后更新: July 23, 2022