题目地址:75. 颜色分类

方法一:单指针,两趟扫描

分析

先对 0 进行排序,排完后再排好的 0 的末端开始,对 1 进行排序。两趟排序下来,一定满足条件。

代码

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

        for (int i = index; i < len; i++) {
            if (nums[i] == 1) {
                swap(nums[index], nums[i]);
                index ++;
            }
        }
    }
};

方法二:【同向】双指针,单趟扫描

分析

可以定义两个指针分别对 0 和 1 进行排序。在此称已排好序的部分为头部,范围 [0, ptr],ptr 为头部的尾部。
设两个指针 p0p1分别对 0、1 进行处理。如果在进行对 0 交换的时候,p0 < p1的话,会将头部中已排好序的 1 替换出去,所以在交换 0 的时候,要特殊判断一下 p0 < p1。而且如果 p0 > p1 的话,将会打乱排序,为了避免这种情况的出现,需要在 nums[i] == 0的条件下,p0 和 p1 都需自增,维护 p0 <= p1

代码

class Solution {
public:
    void sortColors(vector<int>& nums) {
        int len = nums.size();

        int p0 = 0, p1 = 0;

        for (int i = 0; i < len; i++) {
            if (nums[i] == 1) {
                swap(nums[i], nums[p1 ++]);
            } else {
                if (nums[i] == 0) {
                    swap(nums[i], nums[p0]);
                    if (p0 < p1) {
                        swap(nums[i], nums[p1]);
                    }
                    p1 ++;
                    p0 ++;
                }
            }
        }
    }
};

方法三:【对撞】双指着,单趟扫描

分析

设定两个指针p0p2分别对 0 和 2 进行交换处理。p0 位于数组左侧,p2 位于数组右侧。当遍历指针大于 p2 的时候终结循环。

代码

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

            if (nums[i] == 0) {
                swap(nums[i], nums[left]);
                left ++;
            }
        }
    }
};