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

LeetCode 75. 颜色分类 - 双指针法高效解决(Java实现)

文章目录

    • 问题描述
    • 算法思路:三指针分区法
      • 核心思想
      • 指针定义
    • Java实现
    • 算法执行流程
    • 关键问题解析:为什么交换0后不需要重新检查?
      • 交换0时的两种情况分析
      • 详细解释:
    • 复杂度分析
    • 示例演示(输入:[2,0,2,1,1,0])
    • 总结

本文介绍一种时间复杂度O(n)、空间复杂度O(1)的优雅解法,通过双指针技术实现颜色分类的一趟扫描排序

问题描述

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

示例:

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

算法思路:三指针分区法

核心思想

使用三个指针将数组分为四个区域:

  1. [0, p0):已排序的0区域
  2. [p0, curr):已排序的1区域
  3. [curr, p2]:待处理区域
  4. (p2, end]:已排序的2区域

指针定义

  • p0:指向下一个0应放置的位置(0区域的右边界)
  • p2:指向下一个2应放置的位置(2区域的左边界)
  • curr:当前遍历指针,负责处理元素交换

Java实现

class Solution {public void sortColors(int[] nums) {if (nums == null || nums.length < 2) return;int p0 = 0;                   // 0区域右边界int p2 = nums.length - 1;     // 2区域左边界int curr = 0;                 // 当前遍历指针while (curr <= p2) {switch (nums[curr]) {case 0:// 将0交换到0区域swap(nums, curr++, p0++);break;case 1:// 1保留在中间区域curr++;break;case 2:// 将2交换到2区域swap(nums, curr, p2--);// 注意:curr不自增,需检查交换来的新元素break;}}}// 辅助交换函数private void swap(int[] nums, int i, int j) {int temp = nums[i];nums[i] = nums[j];nums[j] = temp;}
}

算法执行流程

  1. 初始化指针

    • p0 = 0(0区域起始位置)
    • p2 = nums.length-1(2区域起始位置)
    • curr = 0(从数组开头遍历)
  2. 元素处理逻辑

    • 遇到0:与p0交换,p0curr右移
    • 遇到1:跳过,curr右移
    • 遇到2:与p2交换,p2左移(curr不变)
  3. 终止条件curr > p2(所有元素处理完毕)

关键问题解析:为什么交换0后不需要重新检查?

交换0时的两种情况分析

情况条件交换前状态交换后状态
情况1curr > p0nums[p0] = 1nums[curr] = 1
情况2curr == p0自身交换保持不变

详细解释:

  1. curr > p0

    • p0位置必定是1(因为0区域和1区域已排序)
    • 交换后curr位置变为1 → 可直接跳过处理(1属于中间区域)
  2. curr == p0

    • 自身交换无实际变化
    • 元素保持0 → 属于已排序区域

结论:交换0后curr位置的新元素只可能是0或1,都无需再次处理,因此可以直接移动curr指针。

复杂度分析

指标说明
时间复杂度O(n)单次遍历完成排序
空间复杂度O(1)仅使用常数级额外空间

示例演示(输入:[2,0,2,1,1,0])

步骤操作数组状态指针变化
1初始状态[2,0,2,1,1,0]p0=0, p2=5, curr=0
2处理2:交换curr↔p2[0,0,2,1,1,2]p2=4
3处理0:交换curr↔p0[0,0,2,1,1,2]p0=1, curr=1
4处理0:交换curr↔p0[0,0,2,1,1,2]p0=2, curr=2
5处理2:交换curr↔p2[0,0,1,1,2,2]p2=3
6处理1:跳过[0,0,1,1,2,2]curr=3
7处理1:跳过[0,0,1,1,2,2]curr=4 > p2(结束)

总结

双指针法解决颜色分类问题的核心在于:

  1. 通过p0p2维护已排序区域
  2. curr指针动态处理待排序区域
  3. 巧妙利用交换操作实现元素归位
  4. 利用数组分区特性优化操作步骤(交换0后无需重检)

该算法是荷兰国旗问题的经典解法,体现了双指针技术在数组原地操作中的高效性,是面试中的高频考点。

http://www.xdnf.cn/news/720577.html

相关文章:

  • unity星空运动
  • ZeroSearch: 无需搜索即可激发LLM的搜索能力
  • Ollama v0.8.0 发布,支持通过工具调用进行流式响应!
  • Powerbuilder 连接达梦数据库(ODBC 和 JDBC)
  • [ Qt ] | Qlabel使用
  • 软考-系统架构设计师-第十章 系统质量属性和架构评估
  • 2025-05-29 学习记录--Python-面向对象
  • Pinia Plungin Persistedstate
  • Shell 脚本基础笔记
  • Java 中的 synchronized 和 Lock:如何保证线程安全
  • 深度解析互联网区(Internet ):架构、风险与防护全攻略
  • iOS 关于上架 4.3a
  • 330130-045-00-00 Bently Nevada 3300 XL延长电缆
  • 软考 系统架构设计师之考试感悟3
  • 美创专家分享医疗数据安全分类分级实践与探索
  • 从“固定“到“流动“:移动充电如何重塑用户体验?
  • 使用grpc建立跨语言通讯
  • Lua语言学习
  • 编译原理OJ平台练习题题解
  • 用 Python 模拟下雨效果
  • 输入输出相关问题 day4
  • CSS--background-repeat详解
  • 数据中台是什么?数据中台解决方案怎么做?
  • Java基于SpringBoot的医院挂号系统,附源码+文档说明
  • Animate CC CreateJS 技术50道测试题目
  • python面向对象
  • NodeJS 基于 Koa, 开发一个读取文件,并返回给客户端文件下载,以及读取文件形成列表和文件删除的代码演示
  • 64、【OS】【Nuttx】任务休眠与唤醒:clock_nanosleep
  • Java类中各部分内容的加载执行顺序
  • 【JS进阶】JavaScript 中 this 值的确定规则