首页/新闻资讯/正文详情

双指针法解决颜色分类问题:LeetCode 75题解析

发布时间:2026/11/5 17:45:53 来源:云帆数科 栏目:资讯中心
双指针法解决颜色分类问题:LeetCode 75题解析
1. 问题背景与核心挑战颜色分类Sort Colors是LeetCode题库中的经典题目编号75。题目要求对包含红、白、蓝三种颜色的数组进行原地排序使得相同颜色相邻且按红、白、蓝顺序排列。这个问题看似简单却蕴含着算法设计的精妙之处。在实际开发中类似场景比比皆是。比如电商平台的商品按价格区间分类、日志系统按紧急程度过滤消息甚至游戏开发中按对象类型批量处理实体。理解这个问题的解法能帮助我们掌握处理分类问题的通用思路。题目给出的约束条件非常关键必须使用原地排序算法空间复杂度O(1)只能遍历数组一次时间复杂度O(n)颜色用整数0、1、2表示这些限制排除了简单的计数排序和标准库sort方法迫使我们寻找更巧妙的解决方案。2. 解法一双指针交换法2.1 基本思路双指针法是解决这类问题的黄金标准。我们维护两个指针left指针标记0红色的右边界right指针标记2蓝色的左边界当前指针i用于遍历数组核心思想是通过交换操作将0移到左侧2移到右侧自然1就会留在中间。public void sortColors(int[] nums) { int left 0, right nums.length - 1; int i 0; while (i right) { if (nums[i] 0) { swap(nums, left, i); } else if (nums[i] 2) { swap(nums, right--, i); } else { i; } } } private void swap(int[] nums, int i, int j) { int temp nums[i]; nums[i] nums[j]; nums[j] temp; }2.2 关键点解析边界条件处理当nums[i]2时i不递增是因为交换过来的元素可能还是2循环终止条件i right而非i nums.length指针移动逻辑只有确认当前元素是1时才移动i注意在面试中面试官通常会要求解释为什么nums[i]2时不递增i。这是最容易出错的地方需要重点准备。3. 解法二计数排序变种3.1 实现方案虽然题目要求原地排序但了解计数排序的变种对理解问题本质很有帮助public void sortColors(int[] nums) { int[] count new int[3]; for (int num : nums) count[num]; int index 0; for (int i 0; i count.length; i) { while (count[i]-- 0) { nums[index] i; } } }3.2 适用场景分析这种方法虽然不满足题目要求但在实际工程中当颜色种类固定且较少时如本例的3种需要稳定排序时允许使用额外空间时是更直观且易维护的选择。面试时可以先提出这种解法再优化为双指针法展示思维过程。4. 算法复杂度对比方法时间复杂度空间复杂度是否原地遍历次数双指针法O(n)O(1)是1计数排序变种O(n)O(k)否2标准库排序O(nlogn)O(logn)视实现多次5. 边界条件与测试用例设计完整的测试应该包含以下场景空数组输入单元素数组全0/全1/全2数组已排序数组逆序数组随机混合数组超大数组性能测试Test public void testSortColors() { // 常规测试 int[] test1 {2,0,2,1,1,0}; sortColors(test1); assertArrayEquals(new int[]{0,0,1,1,2,2}, test1); // 边界测试 int[] test2 {2}; sortColors(test2); assertArrayEquals(new int[]{2}, test2); // 性能测试 int[] largeArray new int[1000000]; // 填充测试数据... }6. 实际工程应用案例6.1 电商价格区间筛选假设我们需要对商品按价格区间快速分类0-100元0100-500元1500元以上2使用双指针法可以在用户滑动筛选条时实时更新商品列表。6.2 日志级别过滤系统日志通常分为ERROR0WARN1INFO2需要快速过滤显示特定级别的日志时同样的算法可以高效处理。7. 常见面试问题与回答策略Q: 为什么nums[i]2时不递增i A: 因为交换过来的元素可能还是2需要再次检查。而交换0时我们可以确定换过来的只能是1因为左边的都已经处理过Q: 如何证明算法的正确性 A: 可以维护循环不变式left左侧全是0right右侧全是2left到i之间全是1Q: 如果颜色增加到5种怎么办 A: 双指针法可以扩展为多指针但更推荐使用计数排序或标准库sortQ: 这个算法是稳定的吗 A: 不是相同颜色的相对顺序可能会改变。如果需要稳定排序应该使用其他方法8. 算法优化与变种8.1 三指针实现对于颜色种类更多的情况可以扩展为三指针// 假设颜色为0,1,2,3 int low 0, mid 0, high nums.length - 1; while (mid high) { if (nums[mid] 0) { swap(nums, low, mid); } else if (nums[mid] 1) { mid; } else if (nums[mid] 2) { swap(nums, mid, high--); } else { // 处理颜色3... } }8.2 并行化处理对于超大数组可以考虑分块并行处理将数组分成k个块每个线程统计自己块内的颜色计数汇总计数后计算每个块的写入位置并行执行写入9. 与其他算法题的关联颜色分类与以下算法题有密切联系移动零LeetCode 283可以看作只有0和非0两种颜色按奇偶排序数组LeetCode 905二进制分类问题荷兰国旗问题完全相同的题目理解这些问题的共性可以建立分类问题的通用解决框架。10. 刷题建议与学习路径对于准备面试的开发者建议先掌握基础的双指针实现理解算法正确性的证明方法练习各种边界条件的测试用例尝试用不同语言实现思考实际工程中的应用场景进阶学习可以关注多指针技巧并行算法优化稳定性与性能的权衡泛型实现如果语言支持这个问题的价值不仅在于解法本身更在于培养分类处理问题的思维方式。在实际工程中类似的需求随处可见掌握这类算法能显著提升代码效率和质量。

相关推荐

AI Agent开发速查清单:LangGraph、AutoGen、CrewAI与MCP核心要点
AI Agent开发速查清单:LangGraph、AutoGen、CrewAI与MCP核心要点

1. 这份速查清单到底解决什么问题做AI应用开发的人大概都有过这种体验:项目里同时用着LangGraph编排流程、AutoGen跑多智能体对话、CrewAI做角色分工,还要接MCP协议打通外部工具,结果每隔两周回头看自己的代码,就得重新翻文档确认… · 2026/11/5 17:45:53

Meta Llama 3 CPU推理优化:从原理到生产部署
Meta Llama 3 CPU推理优化:从原理到生产部署

1. Meta Llama 3 CPU推理优化全景解读当大多数人还在追逐GPU推理的极致性能时,我们团队已经在生产环境中将Llama 3-8B模型成功部署到64核CPU服务器上,实现了每秒18个token的稳定输出。这个数字可能不如高端GPU亮眼,但在成本敏感型业务场景中&… · 2026/11/5 17:45:50

云管理语音网关核心技术解析与选型指南
云管理语音网关核心技术解析与选型指南

1. 语音网关的云管理核心需求解析 在企业数字化转型浪潮中,语音通信系统的云化管理已成为不可逆的趋势。传统PBX设备正在被支持云管理的语音网关逐步替代,这种转变不仅仅是技术架构的升级,更是企业通信模式的根本性变革。 云管理语音网关的核… · 2026/11/3 7:37:03

EasyU优启通PE维护盘实战指南:制作、启动与核心操作全解析
EasyU优启通PE维护盘实战指南:制作、启动与核心操作全解析

1. 为什么一个PE维护盘值得单独拿出来聊装系统、修引导、救数据、清病毒,这些活儿但凡干过几次的人都知道,真正决定效率的往往不是你手速多快,而是手边那套PE环境靠不靠谱。EasyU(圈内习惯叫优启通)就是在这个场景下被… · 2026/11/5 16:49:35

Rust原来很简单二:所有权系统
Rust原来很简单二:所有权系统

Part 2 核心篇 —— 所有权系统 本篇覆盖 第 6 ~ 10 章:所有权、借用与引用、生命周期、字符串与切片、内存模型。 ⚠️ 这是全书最重要的一篇。 把它吃透,Rust 从此“很简单”;跳过它,你会处处碰壁。请慢下来,动手敲每一段代码。 第 6 章 所有权:Rust 的第一性原理 6… · 2026/11/5 16:26:08

基于Hadoop+Spark的民宿智能推荐系统设计与实现
基于Hadoop+Spark的民宿智能推荐系统设计与实现

1. 项目概述:大数据时代的民宿智能推荐这个毕业设计项目融合了当前大数据领域最主流的技术栈,构建了一个完整的民宿推荐系统解决方案。作为一名长期从事大数据系统开发的工程师,我认为这个选题非常贴合实际应用场景——随着旅游业的复苏和共享… · 2026/11/5 14:59:25

ADS122U04IPWR+STM32F427ZI工业级温度测量信号链设计
ADS122U04IPWR+STM32F427ZI工业级温度测量信号链设计

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/5 14:10:41

UART接口24位ADC搭配RS485,解决远距离温度监控难题
UART接口24位ADC搭配RS485,解决远距离温度监控难题

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/5 14:10:41

UART接口24位ADC搭配PIC18F46K22的RTD与热电偶测温实践
UART接口24位ADC搭配PIC18F46K22的RTD与热电偶测温实践

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/5 14:10:41

双极步进电机控制实战:DRV8818PWPR与PIC18F86K22驱动调试
双极步进电机控制实战:DRV8818PWPR与PIC18F86K22驱动调试

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/5 10:27:59

STM32F207ZG + DRV8818PWPR 步进电机驱动实战解析
STM32F207ZG + DRV8818PWPR 步进电机驱动实战解析

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/5 10:28:03

DRV8818PWPR+dsPIC30F4013工业级双极步进电机控制方案
DRV8818PWPR+dsPIC30F4013工业级双极步进电机控制方案

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/5 10:28:07

多智能体协作系统架构设计与实践优化
多智能体协作系统架构设计与实践优化

1. 多智能体协作系统的时代背景2017年Transformer架构的诞生彻底改变了人工智能的发展轨迹。当行业还沉浸在单一大模型带来的性能突破时,Anthropic的研究团队已经将目光投向了更前沿的领域——如何让多个智能体通过协作产生超越单体能力的系统智能。这就像交响乐团中… · 2026/11/5 0:00:39

大模型系统性入门实战指南:从原理到部署微调的全链路路线
大模型系统性入门实战指南:从原理到部署微调的全链路路线

提到大模型的系统性入门,我先说个结论:这事真不难,难的是资料太散、路线太多,今天这个框架明天那个工具,新人很容易在“收藏夹吃灰”和“教程看到一半放弃”之间反复横跳。市面上关于大模型的内容少说有几十万篇&#… · 2026/11/5 0:00:39

鸿蒙文件系统沙箱机制解析与开发实践
鸿蒙文件系统沙箱机制解析与开发实践

1. 鸿蒙文件系统沙箱机制深度解析作为一名从Android转向鸿蒙开发的工程师,我深刻体会到文件系统访问是迁移过程中最先遇到的"拦路虎"。在Android上运行良好的文件读写代码,在鸿蒙真机环境却频频出现文件写入后神秘消失或直接抛出权限拒绝错误的… · 2026/11/5 0:00:39

双极步进电机控制实战:DRV8818PWPR与PIC18F86K22驱动调试
双极步进电机控制实战:DRV8818PWPR与PIC18F86K22驱动调试

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/5 10:27:59

STM32F207ZG + DRV8818PWPR 步进电机驱动实战解析
STM32F207ZG + DRV8818PWPR 步进电机驱动实战解析

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/5 10:28:03

DRV8818PWPR+dsPIC30F4013工业级双极步进电机控制方案
DRV8818PWPR+dsPIC30F4013工业级双极步进电机控制方案

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/5 10:28:07

了解更多?预约专属演示

我们的顾问将为您一对一讲解产品与方案

企业微信二维码