当前位置：首页 > article >正文

LeetCode75. 颜色分类（2024冬季每日一题 40）

article 2024/12/29 5:31:22

给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。

我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

必须在不使用库内置的 sort 函数的情况下解决这个问题。

示例 1：

输入：nums = [2,0,2,1,1,0]
输出：[0,0,1,1,2,2]

示例 2：

输入：nums = [2,0,1]
输出：[0,1,2]

提示：

$n == n u m s . l e n g t h$
$1 <= n <= 300$
$n u m s [i]$ 为 0、1 或 2

进阶：

你能想出一个仅使用常数空间的一趟扫描算法吗？

思路：

扫描两遍，第一遍将 0 全部交换到最前面位置，第二遍将 1 交换到中间位置
用 ptr 记录，当前在数组左边的所有 0 的最后一个下标的下一个位置，下次交换时，将 0 交换到 ptr 指向的位置，初始时ptr=0
交换完后将 ptr ++
第一遍扫描过后，ptr 的位置就是数组中所有 0 的最后一个位置的下一个位置的下标
第二遍扫描从 ptr 位置开始往右扫描（因为左边确定都是0），找出1，然后交换到 ptr 位置，交换完后，ptr ++，使得 1 在全部在 0 和 2 中间

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

思路：

一遍扫描，ptr1 用来记录 0 要放的位置，ptr2 用来记录 1 要放的位置
遍历时，如果当前位置是 0，则将当前位置与 ptr1 交换，并且 ptr1++
- 如果交换完后，当前位置是 1，则将当前位置继续与 ptr2 交换（由于 ptr1 记录 0 的位置，ptr2 记录 1 的位置，所有 ptr1 <= ptr2{0必须在1的前面}，ptr1==ptr2时，说明还没扫描到1）（当ptr1 < ptr2 时，交换 ptr1（此时ptr1肯定等于1），会将1交换到后面，需要将1再放到相应的部分）
- 不论是否满足上面的条件与否，ptr2 都 +1
如果当前位置是 1，则直接与 ptr2 交换，然后 ptr2++

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