【LeetCode热题100道笔记+动画】颜色分类
题目描述
给定一个包含红色、白色和蓝色、共 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的顺序依次填充
算法过程
- 初始化两个计数器zeros和ones，分别记录0和1的出现次数
- 遍历数组，统计0和1的数量（2的数量可通过数组长度减去前两者得到）
- 重新填充数组：
- 前zeros个位置填充0
- 接下来ones个位置填充1
- 剩余位置填充2
时间复杂度
- 时间复杂度：O(n)，需遍历数组两次（n为数组长度）
- 空间复杂度：O(1)，仅使用常数级额外空间
代码
/*** @param {number[]} nums* @return {void} Do not return anything, modify nums in-place instead.*/
var sortColors = function(nums) {const n = nums.length;let zeros = 0, ones = 0;for (let num of nums) {if (num === 0) {zeros++;} else if (num === 1) {ones++;}}for (let i = 0; i < zeros; i++) {nums[i] = 0;}for (let i = 0; i < ones; i++) {