$$\color{Red}{颜色分类【leetcode75 三指针原地排序】}$$

我的网站=> 分享了我关于前后端的各种知识和生活美食~

我于Acwing平台分享的零散刷的各种各样的题

给定一个包含红色、白色和蓝色、共 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 == nums.length
• 1 <= n <= 300
• nums[i] 为 0、1 或 2

进阶：

• 不加限制其实就是普通的排序问题，不管是归并还是快排，想必大家信手拈来，随便写。

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

• 但是加入一趟扫描，直觉上类似计数排序，需要用到双指针了，但是这道题维护了三个颜色，那只能选择三指针分成四段 => 【0, 1, 待排序段, 2】

解析

其实这道题甚至背下来都没难度，很短的代码，但是边界问题说实话考虑下来我觉得对能力提升还是帮助挺大的，要从方法论上学会，而不是单独会做一道题。

一趟扫描，直觉上类似计数排序，需要用到双指针了，但是这道题维护了三个颜色，那只能选择三指针分成四段 => 【0, 1, 待排序段, 2】

具体来说，设置指针 i, j, k

起始位置 i = j = 0 , k = nums.length - 1

我们维护 [0 -> j - 1] 均为 0 的段， [j -> i - 1] 均为 1 的段， [k + 1 -> nums.length - 1] 均为 2 的段。而 [i -> k] 均为暂时没分类的段。

那么开局即满足条件【边界-1 视为不存在元素】

那么分为三种情况进行操作

1. nums[i] == 2 此时应该让 nums[i] 和 nums[k] 互换，并且 k -- ，而 i 位置不变，因为一定能保证 k 自减后

k + 1 -> nums.length - 1 均为 2 的段，但是 交换过来的 nums[i] 未必是 1 ，还需要继续判断 nums[i] 的值加以循环

1. nums[i] == 1 此时应该直接让 i ++ ，因为维护了[j -> i - 1] 均为 1 的段，可判断下一个位置

2. nums[i] == 0 此时应该让 nums[i] 和 nums[j] 互换，并且 i ++ 同时 j ++，【为什么之前 i 不自增此时会自增？】

因为 j 满足 j <= i，一定满足交换前，要么本身两个位置重合，那么此时交换后满足维护的四个区间的合法性，nums[j-1] == 0，且剩下的区间范围均是要求的数字情况。如果交换前不重合，势必满足 nums[i] == 0 && nums[j] == 1 ，交换后的自增前 nums[i] 一定等于 1 了，可自增判断下一个数

那么最终结束循环的 条件 ，应该是 i > k 此时枚举完所有 [i, k] 内未分类的点，均分配到了 0 => [0, j-1] , 1 => [j, i - 1], 2 => [i, nums.length - 1]

当 i == k 其实 nums[i] 这个点还没被分类，所以还需要把这个位置的点进行分类。

至此全部的边界分析完毕，每个指针的细节也都囊括了，应该是最全的题解了。😇

class Solution {
    public static void swap(int [] a, int i, int j) {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }

    public void sortColors(int[] nums) {
        for (int i = 0, j = 0, k = nums.length - 1; i <= k;) {
            if (nums[i] == 2) swap(nums, i, k --);
            else if (nums[i] == 1) i ++;
            else if (nums[i] == 0) swap(nums, i ++, j ++);
        }
    }
}