颜色分类

75. 颜色分类

难度 中等

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

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

Given an array nums with n objects colored red, white, or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white, and blue.

We will use the integers 0, 1, and 2 to represent the color red, white, and blue, respectively.

示例 1：

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

输出：[0,0,1,1,2,2]

示例 2：

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

输出：[0,1,2]

示例 3：

输入：nums = [0]

输出：[0]

示例 4：

输入：nums = [1]

输出：[1]

提示：

• n == nums.length
• 1 <= n <= 300
• nums[i] 为 0、1 或 2

进阶：

• 你可以不使用代码库中的排序函数来解决这道题吗？
• 你能想出一个仅使用常数空间的一趟扫描算法吗？

问题

题目的精髓：时间复杂度 O(n)，空间复杂度 O(1)

• 之前学过的排序算法：
  • 时间复杂度太高：冒泡、选择、插入、归并、希尔、堆
  • 空间复杂度太高：计数排序、基数排序、桶排序
• 直接照搬是不行的

解法

• 合并子序列
  • 归并排序思想
• 双指针法
  • 一般要求 一趟 就搞定什么的问题，很可能要借助双指针，甚至是三指针

双（三）指针法

思路演进

• 从左往右扫一遍

  • 发现 0 放到最左边
  • 发现 2 放到最右边
  • 发现 1 不动

• 用两个指针，分别指向头尾

  • 左侧发现 2 就交换左右指针
  • 右指针左移

• 还要判断一次左指针的新值，因为换过来的也可能是个 2

  • 还是 2：那么再和右指针交换

  • 不是 2：

    • 是 1 ：不作处理，左指针右移，假设遇到一个 0 那么这个 0 应当放到刚才的 1 左边，但是左指针已经移动走了，因此得出结论 需要3指针

• 红色指针扫描数组
  • 遇到 1—— 指针直接右移
  • 遇到 0 —— 跟绿色指针（指0指针）交换，绿色指针++，红色指针++
  • 遇到 2 —— 跟紫色指针（指2指针）交换，紫色指针--，红色指针不动，再次对红色指针的值进行判断，保持红色指针的值不变即可，因为正好会再次进入循环
• 红色指针 > 紫色指针，结束

public class _75颜色分类 {

public void sortColors(int[] nums) {

int green = 0;

int purple = nums.length - 1;

int red = 0;

while (red <= purple) {

if (nums[red] == 0) // 与绿色交换

swap(nums, red++, green++);

else if (nums[red] == 1)

red++;

else // 与紫色交换

swap(nums, red, purple--);

// 再次判断 red 对应的值

// !! 主要不动 red 的值即可实现，因为会再次进入while循环

}

}

private void swap(int[] nums, int i1, int i2) {

int temp = nums[i1];

nums[i1] = nums[i2];

nums[i2] = temp;

}

public static void main(String[] args) {

int[] array = {2, 1, 2, 1, 0, 0};

_75颜色分类 obj = new _75颜色分类();

obj.sortColors(array);

for (int i : array) {

System.out.print(i + " ");

}

}

}