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

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

news 来源：原创 2025/5/18 19:15:45

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

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

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

一、题目回顾：颜色分类到底想考啥？

原题描述：

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

举个栗子：

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

听起来像个排序问题对吧？但重点来了：

要求原地排序，不能用库函数排序，且只遍历一次数组（或尽可能少次）。

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

二、解法一：计数排序，暴力但可靠

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

思路：

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

优点：

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

缺点：

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

三、解法二：双指针法，经典且优雅

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

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

本题中，我们可以维护三段区域：

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

步骤：

初始化指针 p0=0，i=0，p2=n-1；
遍历数组时，根据当前值执行不同策略：
- 如果是 0，交换到 p0 位置，p0 与 i 同时右移；
- 如果是 2，交换到 p2 位置，p2 左移，i 不动（因为换过来的可能是 0，要再判断）；
- 如果是 1，i 右移；
遍历终止条件是 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多半当场就“哇哦”了。

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

颜色分类，不靠“调色盘”：双指针 VS 计数排序的正面PK 在算法圈混得久了，总有一些题目是面试官的心头好，刷题人绕不过的“鬼门关”。“颜色分类”（LeetCode 75）就是其中之一，看似小儿科&#xf…...

编程日记 2025/5/18 19:15:45

Shopify网上商店GraphQL Admin接口查询实战

目录一、Shopify网上商店二、个人商店配置接口权限三、PostMan调用接口测试四、通过Java服务调用接口一、Shopify网上商店 Shopify是由Tobi Ltke创办的加拿大电子商务软件开发商，总部位于加拿大首都渥太华，已从一家在咖啡店办公的 5人团队&…...

编程日记 2025/4/30 13:36:57

Laravel基础

Laravel 基础 01.Laravel入门和安装 Composer安装Laravel步骤要使用 Composer 安装 Laravel，请按照以下步骤操作： 确保已经安装了 Composer。如果还没有安装，请访问 https://getcomposer.org/download/ 下载并安装。打开命令行或终端。…...

编程日记 2025/5/18 19:04:29

【Leetcode 每日一题 - 补卡】2302. 统计得分小于 K 的子数组数目

问题背景一个数组的分数定义为数组之和乘以数组的长度。比方说， [ 1 , 2 , 3 , 4 , 5 ] [1, 2, 3, 4, 5] [1,2,3,4,5] 的分数为 ( 1 2 3 4 5 ) 5 75 (1 2 3 4 5) \times 5 75 (12345)575。给你一个正整数数组 n u m s nums nums 和一个整数 k…...

编程日记 2025/4/30 13:34:47

力扣——206.反转链表倒序输出链表

206. 反转链表 - 力扣（LeetCode） 思路（迭代） 设三个指针，前后两个指针都为空，当前指针为输入的头指针开始循环——判断条件为当前节点不为空先给下一个节点赋值为——当前节点的下一个改变当前节点的…...

编程日记 2025/4/30 13:33:43

Arthas在Java程序监控和分析中的应用

Arthas在Java程序监控和分析中的应用在互联网大厂Java求职者的面试中，经常会被问到关于使用Arthas来监控和分析Java程序的相关问题。本文通过一个故事场景来展示这些问题的实际解决方案。第一轮提问面试官：马架构，欢迎来到我们公司的面…...

编程日记 2025/4/30 13:32:40

第13讲：图形尺寸与分辨率设置——适配论文版面，打造专业图稿！

目录 📌 为什么这一讲重要？ 🎯 一、先认识几个关键词 ✍️ 二、ggsave() 是导出图的标准方法 📐 三、尺寸设置技巧：对齐目标期刊 🔍 找到目标期刊的图形栏宽 📦 四、多个图组合导出（与 patchwork 搭配） 🧪 五、使用 Cairo / ragg 导出高质量图 🎁 六…...

编程日记 2025/4/30 13:30:30

Docker与Vmware网络模式的对别

前言在使用了很久的VMware和Docker后，分别独立配置过他们的网络，但是每次配置一方时，总感觉和另一方有点不一样，但是也没有来得及总结。刚好最近有时间可以总结一下。重点： 1、VMware的桥接模式和Docker的桥接模式完…...

编程日记 2025/4/30 13:28:16

大模型在肾癌诊疗全流程中的应用研究报告

目录一、引言 1.1 研究背景与意义 1.2 研究目的与方法 1.3 国内外研究现状二、大模型预测肾癌术前情况 2.1 基于影像组学的肾癌良恶性及分级预测 2.1.1 MRI 影像组学模型预测肾透明细胞癌分级 2.1.2 CT 影像深度学习模型鉴别肾肿物良恶性及侵袭性 2.2 大模型对手术风…...

编程日记 2025/4/30 13:28:15

Springboot使用登录拦截器LoginInteceptor来做登录认证

创建拦截器LoginInteceptor类 interceptors/LoginInteceptor.java package org.example.interceptors;import jakarta.servlet.http.HttpServletRequest; import jakarta.servlet.http.HttpServletResponse; import org.example.utils.JwtUtil; import org.springframework.s…...

编程日记 2025/4/30 13:27:08

2025年- H13-Lc120-189.轮转数组（普通数组）---java版

1.题目描述 2.思路 import java.util.Arrays;public class H189 {public static void main(String[] args) {int[] newArr {1, 2, 3, 4, 5};int[] nums new int[5];System.arraycopy(newArr,0,nums,0,4);System.out.println(Arrays.toString(nums)); } }补充2： 3.…...

编程日记 2025/4/30 13:26:05

Android Framework常见问题

以下是不同难度级别的 Android Framework 面试题，包含答案要点，可帮助你为面试做好准备。初级难度 1. 请简要解释 Android Framework 是什么。答案要点：Android Framework 是 Android 系统的核心组成部分，它为开发者提供了一…...

编程日记 2025/4/30 13:26:04

【AI】图片处理的AI工具

博主最近需要给客户展示一下做的一些设备和仪器，随手拍了一些照片，觉的背景不是很好看，于是在网上寻找AI图片处理工具。后来随手用了一下豆包AI，发现很好用，这里把一点使用的心得体会记录一下，并和大家分享…...

编程日记 2025/4/30 13:24:58

Python列表全面解析：从基础到高阶操作

一、为什么需要列表？ 在Python中，列表是可变有序序列，用于存储多个元素的容器。相较于单一变量存储独立值，列表能更高效地管理批量数据，其特点包括： 引用存储：列表元素存储的是对象的引用…...

编程日记 2025/4/30 13:23:53

C++调用C动态库编译时报undefined reference to “funcxxx“错误

问题描述：Linux平台上C调用C库进行make编译时报undefined reference to "funcxxx"错误，错误实例如下： /usr/bin/ld: CMakeFiles/dialog.dir/widgets/widget.cpp.o: in function Widget::loadVerificationModule(): /home/zhangxia…...

编程日记 2025/4/30 13:23:52

基于Spring Boot+Vue 网上书城管理系统设计与实现(源码+文档+部署讲解）

技术范围：SpringBoot、Vue、SSM、HLMT、Jsp、PHP、Nodejs、Python、爬虫、数据可视化、小程序、安卓app、大数据、物联网、机器学习等设计与开发。主要内容：免费功能设计、开题报告、任务书、中期检查PPT、系统功能实现、代码编写、论文编写和辅导、论文…...

编程日记 2025/4/30 13:23:51

C++ 中自主内存管理 new/delete 与 malloc/free 完全详解

C 中 new/delete 与 malloc/free 完全详解一、new/delete 与 malloc/free 的区别特性new/deletemalloc/free属于C语言C语言申请的内存区堆（Heap）堆（Heap）返回类型指向对象类型的指针（自动转换）void*&…...

编程日记 2025/4/30 13:21:41

Maven中的依赖管理

目录什么是依赖范围什么是依赖传递依赖范围对依赖传递的影响依赖冲突什么是依赖冲突依赖冲突的解决方案版本锁定短路径优先编辑声明优先特殊优先（后来者居上） 可选依赖排除依赖可选依赖和排除依赖的区别刷新依赖的8种方式…...

编程日记 2025/4/30 13:21:39

生态修复项目管理软件

在“双碳”目标与生态文明建设的双重驱动下，生态修复项目正成为全球环境治理的核心战场。然而，矿山复绿、湿地修复、水土保持等工程往往面临跨地域、多主体、长周期的管理难题——从数据分散到进度失控，从成本超支到风险频发，传统…...

编程日记 2025/5/18 18:59:39

深度剖析 RocketMQ 5.0 之架构解析：云原生架构如何支撑多元化场景？

拓展学习：🔍「RocketMQ 中文社区」持续更新，提供 RocketMQ 领域专家模型的 AI 答疑作者 | 隆基简介： 了解 RocketMQ 5.0 的核心概念和架构概览；然后我们会从集群角度出发，从宏观视角学习 RocketMQ 的管…...

编程日记 2025/5/18 19:10:33

Spring中bean的生命周期(笔记）

bean的生命周期，按照最重要五步第一步：实例化bean,调用无参构造方法（通过BeanDefinition利用反射实例化Bean对象(无参数构造方法) 并通过推断构造方法...并放入三级缓存中..） 第二步：给bean属性赋值（调用…...

编程日记 2025/5/18 19:09:09

transform-实现Encoder 编码器模块

Encoder 论文地址 https://arxiv.org/pdf/1706.03762 Encoder结构介绍 Transformer Encoder是Transformer模型的核心组件，负责对输入序列进行特征提取和语义编码。通过堆叠多层结构相同的编码层（Encoder Layer），每层包含自注意力机…...

编程日记 2025/4/30 13:19:15

LVGL -窗口操作

1 窗口背景介绍在 LVGL 中，screen 是一个顶层对象，代表你设备上当前显示的整个画面。它相当于一个“全屏容器”，你可以在上面添加按钮、标签、图像、容器等各种界面控件。它的本质就是一个特殊的 lv_obj_t，但它没有父对象&#…...

编程日记 2025/5/18 19:07:31

ollama运行qwen3

环境 windows server GPU 32G 内存 40G 升级ollama 需要版本 0.6.6以上 ollama --version拉取模型 ollama pull qwen3:32b时间比较长，耐心等待运行模型 ollama run qwen3:32b运行起来之后发现GPU是可以跑起来的,发个你好看看默认是深度思考的，不…...

编程日记 2025/4/30 13:18:07

如何查看和验证AWS CloudFront的托管区域ID

在使用AWS Route 53设置DNS记录时，正确识别CloudFront分发的托管区域ID是至关重要的。本文将详细介绍几种查看和验证CloudFront托管区域ID的方法，特别关注中国区CloudFront的特殊情况。为什么托管区域ID很重要？托管区域ID是AWS服务中的一个关键标识符。在创建指向CloudF…...

编程日记 2025/4/30 13:18:04

yum 安装 ncurses-devel 报错 baseurl 的解决方法

解决 yum 安装 ncurses-devel 报错（baseurl 问题） 出现 yum install ncurses-devel 报错 Cannot find a valid baseurl for repo: centos-sclo-rh/x86_64 的原因，很可能是因为 CentOS 7 的 SCL 源在 2024 年 6 月 30 日停止维护了。以下是解…...

编程日记 2025/5/18 18:59:39

《Vue3学习手记7》

组件通信（续） $attrs 组件通信：$attrs 适用于祖传孙或孙传祖 （需要通过中间组件） 传递给后代的数据，但未被接收，都保存在attrs中 1.祖传孙父组件： <template><div cl…...

编程日记 2025/5/18 19:12:12

算法备案类型解析：如何判断你的算法属于哪种类型？

根据《互联网信息服务算法推荐管理规定》政策，算法备案已经成为了强制性备案。但对于企业而言，如何准确判断自身算法所属的备案类型往往存在困惑，今天我们就来详细盘一盘算法备案的类型，教你如何判断自己的算法属于哪一类一、算…...

编程日记 2025/5/18 19:12:12

Javascript 中作用域的理解?

一、作用域的类型 1. 全局作用域（公司大门外） 范围：整个 JavaScript 文件变量：像贴在公告栏上的信息，所有人可见例子：const companyName "阿里"; // 全局变量，任何地方都能访问 fu…...

编程日记 2025/5/18 19:02:50

Qt入门——什么是Qt?

Qt背景介绍什么是Qt? Qt 是⼀个跨平台的 C 图形用户界面应用程序框架。它为应用程序开发者提供了建立艺术级图形界面所需的所有功能。它是完全面向对象的，很容易扩展。Qt 为开发者提供了⼀种基于组件的开发模式 ，开发者可以通过简单的拖拽和组合…...

编程日记 2025/5/18 19:14:05

Snap7西门子PLC通信协议

S7协议，作为西门子的专有协议，广泛应用于多种通讯服务中，如PG通讯、OP通讯以及S7基本通讯等。它独立于西门子的各种通讯总线，能够在MP、PROFIBUS、Ethernet以及PROFINET等多种网络上运行。S7协议实质上是一个由多种应用层协议构成…...

编程日记 2025/4/30 13:06:08

GTC Taipei 2025 医疗域前瞻：从AI代理到医疗生态，解码医疗健康与生命科学的未来图景

引言 2025年，全球医疗健康领域正经历一场由人工智能、机器人技术与分布式计算驱动的范式转移。随着NVIDIA及其生态伙伴在GTC Taipei 2025大会上的深度布局，医疗行业的核心趋势愈发清晰：AI代理程序（Digital AI Agents）赋能临床协作、医疗大数据与精准医学加速落地、医学影…...

编程日记 2025/5/18 19:02:50

C++的vector中emplace_back() 与 push_back() 的区别

C 中 vector 的 emplace_back() 和 push_back() 均用于向容器末尾添加元素，但二者在实现和效率上有显著区别： 1. 参数传递方式 push_back()：接受一个已构造的对象（左值或右值），将其拷贝或移动到容器中。 s…...

编程日记 2025/5/18 19:07:31

LangChain4j +DeepSeek大模型应用开发——5 持久化聊天记忆 Persistence

默认情况下，聊天记忆存储在内存中。如果需要持久化存储，可以实现一个自定义的聊天记忆存储类，以便将聊天消息存储在你选择的任何持久化存储介质中。 1. 存储介质的选择大模型中聊天记忆的存储选择哪种数据库，需要综合考虑数据特…...

编程日记 2025/5/18 19:05:57

C++核心编程 1.2 程序运行后

1.2 程序运行后栈区： 由编译器自动分配释放, 存放函数的参数值,局部变量等注意事项：不要返回局部变量的地址，栈区开辟的数据由编译器自动释放 int * func() {int a 10;return &a; }int main() {int *p func();cout << *p <…...

编程日记 2025/4/30 13:01:48

小市值策略复现（A股选股框架回测系统)

相关config配置 https://quantkt.com/forumDetail?id201043 很早就知道了小市值模型，正好量化选股回测框架出来了，把最裸的小市值复现下，顺便验证下框架逻辑。科普: 小市值策略基于 “小市值效应”，即从历史数据来看&#xf…...

编程日记 2025/4/30 13:01:45

C语言(6)—函数递归

文章目录一、递归的基本概念1.1 什么是递归1.2 递归的核心思想1.3 递归的必要条件二、递归的经典应用2.1 阶乘计算三、递归与迭代的比较3.1 递归的优缺点3.2 迭代的优缺点四、递归的底层机制4.1 函数调用栈4.2 栈溢出风险五、递归优化技巧5.1 记忆化（Memoizati…...

编程日记 2025/4/30 13:01:44

【网络】HTTP报文首部字段

目录一. 预备知识 1.1.代理、网关和隧道 1.1.1.代理 1.1.2.网关 1.1.3.隧道 1.2.保存资源的缓存 1.2.1.缓存的有效期限 1.2.2.客户端的缓存 1.3.用单台虚拟主机实现多个域名二. HTTP首部字段 2.1.HTTP 首部字段格式 2.2.四种 HTTP 首部字段类型三. HTTP通用首部…...

编程日记 2025/5/18 19:01:10

【Fifty Project - D20】

今日完成记录 TimePlan完成情况7：30 - 11：30收拾行李闪现广州 & 《挪威的森林》√10：00 - 11：00Leetcode√16：00 - 17：00健身√ Leetcode 每日一题每日一题来到了滑动窗口系列，今天是越…...

编程日记 2025/5/18 19:02:49

【Linux系统】systemV共享内存

system V共享内存在Linux系统中，共享内存是一种高效的进程间通信（IPC）机制，它允许两个或者多个进程共享同一块物理内存区域，这些进程可以将这块区域映射到自己的虚拟地址空间中。共享内存区是最快的IPC形式。一旦这…...

编程日记 2025/4/30 12:58:24

【计算机网络】DHCP——动态配置ip地址

DHCP 是什么？ DHCP（Dynamic Host Configuration Protocol，动态主机配置协议） 是一种网络协议，用于自动分配 IP 地址和其他网络配置参数（如子网掩码、默认网关、DNS 服务器等）给网络中的设备&…...

编程日记 2025/5/18 19:09:09

TDengine 订阅不到数据问题排查

简介 TDengine 在实际生产应用中，经常会遇到订阅程序订阅不到数据的问题，总结大部分都为使用不当或状态不正确等问题，需手工解决。查看服务端状态通过 sql 命令查看有问题的 topic 和consumer_group 组订阅是否正常。 select * from inf…...

编程日记 2025/5/18 19:15:45

低版的spring boot 1.X接入knife4j

低版的spring boot 1.X接入knife4j 老的项目是用spring boot 1.5.10.RELEASE 不好升级 ，原来接口文档一直用的是老的swagger样式，不是很好看，网上查了下，发现有个knife4j挺好看的，用一下他们的样式，下面是…...

编程日记 2025/5/18 19:01:09

outlook for mac本地邮件存放在哪儿?

尽管 PST 格式通常与 Microsoft Outlook 联系在一起，但认为它也在 Mac OS 上存储邮箱数据是一种误解。实际上，Outlook for Mac 不会将邮件存储为 PST 文件。无法在 Outlook for Mac 中找到 PST 文件位置，因为它不使用 PST 文件来存储邮箱数据…...

编程日记 2025/4/30 12:55:08

javascript＜——＞进阶

一、作用域：变量可以被访问的范围 1.局部作用域 1.1函数作用域在函数内部声明的变量，在函数内部被访问的，外部无法直接访问。总结：1、函数内部声明的变量，在函数外部无法直接访问 2、函数的参数也是函数内部的局…...

编程日记 2025/4/30 12:54:04

Java练习8

一.题目二.源码 package TestRuMen;import java.util.Random; import java.util.Scanner;public class Test11 {public static void main(String[] args){// 调用 createNumber 方法生成一组随机的中奖号码int[] arrcreateNumber();// 调用 userInputNumber 方法获取用户输入…...

编程日记 2025/5/18 19:04:29

C语言按位操作符

在C语言中，按位操作符直接对整数的二进制位（bit）进行操作，常用于底层编程、硬件控制或性能优化场景。以下是按位操作符的详细说明和用法： 1. 按位操作符列表操作符名称功能描述示例&按位与对应位均为1时结果为1&…...

编程日记 2025/5/18 19:04:30

Linux（权限管理）

权限概述基本概念定义：Linux权限是操作系统对用户和进程访问资源进行精细化管控，通过读（r4）、写（w2）、执行（x1）三种基础权限组合实现。其中在运维的角度看它们所对应的操作权限…...

编程日记 2025/4/30 12:52:53

Redis入门到实战——基础篇

一、初识Redis 1. 认识NoSQL 2. 认识Redis Redis诞生于2009年，全称Remote Dictionary Server，远程词典服务器，是一个基于内存的键值型NoSQL数据库。特征： 键值型（key-value），value支持多种…...

编程日记 2025/5/18 19:10:33

ctf.show 卷王杯 pwn签到

pwn签到 64位 ret2libc pwn签到 (1) motalymotaly-VMware-Virtual-Platform:~/桌面$ file pwn pwn: ELF 64-bit LSB executable, x86-64, version 1 (SYSV), dynamically linked, interpreter /lib64/ld-linux-x86-64.so.2, for GNU/Linux 3.2.0, BuildID[sha1]0953abcf1dd6…...

编程日记 2025/4/30 12:50:45

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

一、题目回顾：颜色分类到底想考啥？

二、解法一：计数排序，暴力但可靠

思路：

优点：

缺点：

三、解法二：双指针法，经典且优雅

本题中，我们可以维护三段区域：

步骤：

优点：

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

举例演示：

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

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

相关文章：