当前位置: 首页> 财经> 股票 > 石家庄的疫情情况 最新消息_互联网公司排名图_泽成杭州seo网站推广排名_公司企业网站开发

石家庄的疫情情况 最新消息_互联网公司排名图_泽成杭州seo网站推广排名_公司企业网站开发

时间:2025/7/11 7:32:59来源:https://blog.csdn.net/weixin_46178278/article/details/147615815 浏览次数:0次
石家庄的疫情情况 最新消息_互联网公司排名图_泽成杭州seo网站推广排名_公司企业网站开发

颜色分类,不靠“调色盘”:双指针 VS 计数排序的正面PK


在算法圈混得久了,总有一些题目是面试官的心头好,刷题人绕不过的“鬼门关”。“颜色分类”(LeetCode 75)就是其中之一,看似小儿科,其实暗藏杀机。

你以为它就是个数组排序?错!这道题真要靠你用逻辑+策略去取胜,不是直接一个 sort() 一行干完的事。今天我就带你深入剖析两种主流解法:计数排序双指针法(也叫三路快排变体)


一、题目回顾:颜色分类到底想考啥?

原题描述:

给定一个包含红色、白色和蓝色(分别用 0、1 和 2 表示)的数组 nums,请你原地对它进行排序,使得相同颜色的元素相邻,并按照红、白、蓝的顺序排列。

举个栗子:

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

听起来像个排序问题对吧?但重点来了:

要求原地排序,不能用库函数排序,且只遍历一次数组(或尽可能少次)

这就限制了常规的快速排序、归并排序,逼得我们得从“计数”或“指针走位”下手。


二、解法一:计数排序,暴力但可靠

这个方法很像“先过一遍数一数颜色,再照着配色方案重刷一遍墙”。

思路:

  1. 第一次遍历:统计 0、1、2 出现的次数;
  2. 第二次遍历:按次数把对应颜色写回数组。

优点:

  • 思路简单,代码易写,适合“开局不懂策略”的同学。

缺点:

  • 遍历了两次数组,不够“优雅”;
  • 如果换成 100 种颜色?你统计都得累死。

三、解法二:双指针法,经典且优雅

我们来重点聊聊这个算法圈“万金油”——双指针策略在本题的变体应用。

双指针本质上是一种左右协同、互不干扰的处理方式,用来在遍历中同时维护多个区段。

本题中,我们可以维护三段区域:

[0...p0] 全是0(红色)
[p0+1...i-1] 全是1(白色)
[i...p2] 未处理区域
[p2+1...n-1] 全是2(蓝色)

步骤:

  1. 初始化指针 p0=0i=0p2=n-1
  2. 遍历数组时,根据当前值执行不同策略:
    • 如果是 0,交换到 p0 位置,p0i 同时右移;
    • 如果是 2,交换到 p2 位置,p2 左移,i 不动(因为换过来的可能是 0,要再判断);
    • 如果是 1,i 右移;
  3. 遍历终止条件是 i > p2

优点:

  • 真·原地排序;
  • 只遍历一次数组,效率高;
  • 不依赖辅助数组或额外空间。

四、代码实现:每行都讲给你听

这里我把双指针法代码贴出来,并逐行解释:

def sortColors(nums):# p0指向应该放0的位置,p2指向应该放2的位置p0, i, p2 = 0, 0, len(nums) - 1while i <= p2:if nums[i] == 0:# 遇到0,和p0位置交换,0就安顿好了nums[i], nums[p0] = nums[p0], nums[i]p0 += 1i += 1elif nums[i] == 2:# 遇到2,和p2位置交换,但i不动(因为换来的不确定)nums[i], nums[p2] = nums[p2], nums[i]p2 -= 1else:# 遇到1就跳过,已经在中间的家了i += 1

举例演示:

比如 nums = [2,0,2,1,1,0]

我们会经历以下几个状态:

  • 初始:[2,0,2,1,1,0]
  • 第一步:遇到2,换到末尾 → [0,0,2,1,1,2]
  • 第二步:遇到0,换到p0 → [0,0,2,1,1,2]
  • 最终:[0,0,1,1,2,2]

是不是很像“三向切分的快速排序”?没错,这就是Dijkstra三路划分算法的具体应用。


五、什么时候选哪种方法?

场景推荐算法理由
颜色种类极少(0/1/2)双指针法高效,遍历一遍,原地处理
颜色种类多(如100种)计数排序可扩展性强,不容易混乱
不要求原地普通排序sort() 一行写完,图个快

六、最后总结一下,老朋友

“颜色分类”这题其实是一道考察“数组变换思维”的经典题,你可以把它当作:

  • 熟悉双指针的训练场;
  • 分区思想(类似荷兰国旗问题)的实战;
  • 计数排序在小范围内的应用模型。

别小看这类题,它不是考你写出代码,而是考你理解数据结构如何流转,用最小的资源达到最优解。真正面试遇到类似题,你能当场写出三种方法,优缺点一说,HR多半当场就“哇哦”了。

关键字:石家庄的疫情情况 最新消息_互联网公司排名图_泽成杭州seo网站推广排名_公司企业网站开发

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: