当前位置：首页 > news >正文

【每天学习一点算法 2026/03/21】颜色分类

news 2026/3/26 23:03:40

每天学习一点算法 2026/03/21

题目：颜色分类

给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
必须在不使用库内置的 sort 函数的情况下解决这个问题。

常规的排序算法我这里就不多讲了，我的另一篇文章前端算法基础里面有写（包括冒泡、选择、插入、快速）。

因为这个数组里面只有三种元素，所以我们可以采用一些比较，特殊的方法：简单的说就是 1 放中间 0 和 2 放两边。

/** Do not return anything, modify nums in-place instead. */functionsortColors(nums:number[]):void{if(nums.length<2)return// 只有一项不用排序letwhiteStart=0// 白色插入位置constres:number[]=[]// 存放排序后数组for(leti=0;i<nums.length;i++){if(nums[i]===0){// 0 放在前面，白色插入位置后移res.unshift(0)whiteStart++continue}if(nums[i]===1){// 1 直接在 whiteStart 处插入res.splice(whiteStart,0,1)continue}if(nums[i]===2){// 2 直接放在最后res.push(2)continue}}// 修改元素res.forEach((item,index)=>{nums[index]=item})};

但是这个不是纯粹的原地排序，我们可以在这个基础上调整一下，因为我们移动 2 的时候遍历指针需要停在原地，所以需要一个 count 来辅助遍历。

functionsortColors(nums:number[]):void{if(nums.length<2)returnletcount=nums.length// count 初始为数组长度for(leti=0;i<count;i++){if(nums[i]===0){// 0 取出来放在前面// 虽然取出了一项，但是放在前面了所以不用处理nums.splice(i,1)nums.unshift(0)continue}if(nums[i]===1){// 1 直接不处理continue}if(nums[i]===2){// 2 取出来放在后面nums.splice(i,1)nums.push(2)// 指针不动，遍历边界减 1，防止重复遍历 push 的 2i--count--continue}}};