[LC]75. 颜色分类

🚩传送门：力扣题目

题目

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

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

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

示例 1：

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

示例 2：

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

解题思路：双指针

指针 ：保证区域 全是 红色
指针 ：保证区域全是 蓝色

指针 ：遍历数组，遇到就和指针 交换，遇到就和指针 交换，需要对交换过来的 或者 再次判断，当且仅当 时结束判断。

• 当时说明不需要和指针 或者指针 交换
• 当时说明交换过来的 已经完成了判断，此时应该
• 当时说明越界了，此时遍历结束，数组有序

复杂度分析

时间复杂度： ，其中 是 的长度。

空间复杂度：

官方代码

class Solution {
    public static void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
    public static void sortColors(int[] nums) {
        int i = 0, j = nums.length - 1;
        int index = 0;
        while (i <= index && index <= j) {
            do {
                if (nums[index] == 0) {
                    swap(nums, i++, index);
                } else if (nums[index] == 2) {
                    swap(nums, j--, index);
                }
            } while (i <= index && index <= j && nums[index] != 1);    // 需要对交换过来的nums[i]||nums[j]再次判断
            index++;
        }
    }
}