[数据结构与算法]75. 颜色分类

题目

力扣

思路 计数排序

记下每个元素出现的次数，再从头到尾修改nums里的元素。

代码

class Solution {
public:
    void sortColors(vector<int>& nums) {
        vector<int> cnt(3);
        for(int num : nums)
            cnt[num]++;
        int count = 0;
        for(int i = 0; i < 3; i++){
            for(int j = 0; j < cnt[i]; j++){
                nums[count++] = i;
            }
        }
    }
};

思路 单指针

用ptr标记开头，从前往后移动，把0全都移到前面来。再用ptr标记结尾，从后往前移动，把2全都移到后面。

代码

class Solution {
public:
    void sortColors(vector<int>& nums) {
        int n = nums.size();
        int ptr = 0;
        for(int i = 0; i < n; i++){
            if(nums[i] == 0){
                swap(nums[i], nums[ptr]);
                ptr++;
            }
        }
        ptr = n - 1;
        for(int i = n - 1; i >= 0; i--){
            if(nums[i] == 2){
                swap(nums[i], nums[ptr]);
                ptr--;
            }
        }
    }
};

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