leetcode75：颜色分类

题目链接

leetcode

题目描述

给定一个包含红色、白色和蓝色、共n个元素的数组nums ，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
整数0、 1 和 2分别表示红色、白色和蓝色。
在不使用库内置的 sort 函数的情况下解决这个问题。

C++ 代码

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

/*
    三路快排，荷兰国旗
    
    三个指针：
    lt：指向 0 的最右边界，所有在 lt 左边的元素都是 0
    gt：指向 2 的最左边界，所有在 gt 右边的元素都是 2
    i：当前遍历指针，中间的是 1

    时间复杂度：O(n)
    空间复杂度：O(1)
*/
class Solution_1 {
public:
    void sortColors(vector<int>& nums) {
        int n = nums.size();
        int lt = 0, gt = n-1, i = 0;

        while (i <= gt) {
            if (nums[i] == 0) {
                swap(nums[i], nums[lt]);
                i++;
                lt++;
            } else if (nums[i] == 1) {
                i++;
            } else if (nums[i] == 2) {
                swap(nums[i], nums[gt]);
                gt--;
            }
        }
    }
};

/*
    计数排序
    统计 3 种颜色的个数，可以推广到多个颜色。

    时间复杂度：O(n)
        其中 n 是数组的长度，k 是数组中不同颜色的数量。
        遍历了两次数组，时间复杂度是 O(n)。
    空间复杂度：O(1)
        k 个元素记录颜色的数量，空间复杂度是 O(k)。
        k = 3，空间复杂度是 O(log3)，简化为 O(1)。
*/
class Solution {
public:
    void sortColors(vector<int>& nums) {
        int count[3] = {0};
        for (const int& num : nums) {
            count[num]++;
        }

        for (int i = 0; i < nums.size(); i++) {
            if (i < count[0]) {
                nums[i] = 0;
            } else if (i - count[0] < count[1]) {
                nums[i] = 1;
            } else {
                nums[i] = 2;
            }
        }
    }
};

// 辅助函数：打印数组
void printArray(const vector<int>& nums) {
    cout << "[";
    for (size_t i = 0; i < nums.size(); i++) {
        cout << nums[i];
        if (i != nums.size() - 1) cout << ",";
    }
    cout << "]";
}

int main() {
    Solution solution;
    vector<vector<int>> nums_cases = {
        {2,0,2,1,1,0},
        {2,0,1}
    };

    for (int i = 0; i < nums_cases.size(); i++) {
        auto& nums = nums_cases[i];

        cout << "Input: nums = ";
        printArray(nums);
        cout << endl;
        solution.sortColors(nums);
        cout << "Output: ";
        printArray(nums);
        cout << endl;
    }
    
    return 0;
}