75. 颜色分类

题意

给定一个包含红色、白色和蓝色、共 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]

分析

题目的最后一句话，很容易误导我们走上排序算法的“不归路”，从而想到快速排序，但是

快速排序算法真的是最优解吗？

并不是！

因为即便是快速排序，最快也只能够做到$ O(n) $，但是有一种更快的排序算法——桶

排！

我们可以利用一个 int[] bucket 来记录每个数字出现的次数，例如：如果 5 出现了 3 次，

那么 bucket[5]就等于 3。

基于这样的想法，我们只需要遍历一次 nums[]，就能得出每个数字到底有几个，然后再

遍历 bucket[]将其中的数字依次按照数量取出来，不就能够在$ O(n) $的时间内解决问题

了吗？

是的，这样看起来，桶排是不是非常优秀？比快速排序还优秀的时间复杂度，是不是就可

以无脑替换掉快排呢？

不行！

仔细观察一下，影响桶排的最重要因素，是 nums[]的值域范围！

假设我们有一个数 21474843647，那是不是意味着 bucket[]的大小就要是……

是的，桶排的时间复杂度不仅仅由 nums[]的长度决定，还由 nums[]的值域范围决定。

然而这道题目，nums[i]的可能取值只有 0,1,2，所以我们可以放心大胆地使用桶排。

class Solution {

public void sortColors(int[] nums) {

int[] cnt = new int[3];

for (int num : nums) cnt[num]++;

for(int i = 0;i < cnt[0];i++)

nums[i] = 0;

for(int i = cnt[0];i < cnt[0] + cnt[1];i++)

nums[i] = 1;

for(int i = cnt[0] + cnt[1];i < cnt[0] + cnt[1] + cnt[2];i++)

nums[i] = 2;

}

}

1677504376665-5f63d32a-498d-4028-834c-ae845f57f3ae.png

总结

各种排序均有各自的优势，我们需要在特定的场景选择特定的排序算法，发挥其最大的作

用。

力扣链接：https://leetcode.cn/problems/sort-colors/

一步一个脚印

不积跬步无以至千里，不积小流无以成江海。LeetCode - 100 天从算法小白到卷王正式启

动了，我们计划周一到周五至少每天更新一篇，周六周日更新一篇，目标 300 道

LeetCode 经典题。

PDF 版本目前只针对二哥编程星球的球友开放，如果你也想一起打卡学习算法的话，戳链

接加入我们吧。

一个人可以走得很快，但一群人才能走得更远。二哥编程星球（目前已有 1800 多名球友

加入）里面的每个球友都非常的友善，除了鼓励你，还会给你提出合理的建议，一起冲！

更新: 2023-03-02 08:58:43

原文: https://www.yuque.com/itwanger/czfoq9/dmlggg