Leetcode 颜色分类
这个算法采用了荷兰国旗问题(Dutch National Flag Problem)的解法思想,用三个指针将数组中的元素分为三个区域,并且对这些区域进行动态调整,达到排序的目的。
算法思想:
-
三个指针:
low
指针表示当前0应该存放的区域的边界。mid
指针用来遍历数组,每次检查当前位置的元素。high
指针表示当前2应该存放的区域的边界。
-
算法步骤:
- 开始时,
low
和mid
都指向数组的开头,high
指向数组的末尾。 - 遍历数组,当
mid
小于等于high
时:- 如果
nums[mid] == 0
,表示当前元素是红色(0),应该放到数组的前面,所以与low
交换,low
和mid
同时右移一位。 - 如果
nums[mid] == 1
,表示当前元素是白色(1),不需要移动,mid
右移一位。 - 如果
nums[mid] == 2
,表示当前元素是蓝色(2),应该放到数组的末尾,所以与high
交换,并将high
左移一位,而mid
不动,等待交换后的元素检查。
- 如果
- 开始时,
-
循环结束条件:
- 当
mid
指针超过high
时,说明所有的元素都已经按照红、白、蓝的顺序排列完毕。
- 当
关键点:
- in-place 排序:这个算法不需要额外的空间,直接在原数组上进行排序。
- 时间复杂度:每个元素最多被遍历一次,因此时间复杂度是 O(n),其中 n 是数组的长度。
- 空间复杂度:由于只使用了常数级别的额外空间,空间复杂度为 O(1)。
例子:
假设输入数组是 [2,0,2,1,1,0]
:
- 初始化
low = 0
,mid = 0
,high = 5
。 - 第一次遍历
nums[mid] = 2
,交换nums[mid]
和nums[high]
,数组变为[0,0,2,1,1,2]
,high
左移。 - 第二次遍历
nums[mid] = 0
,交换nums[mid]
和nums[low]
,low
和mid
右移,数组不变。 - 持续遍历并根据上述逻辑调整,最终数组为
[0,0,1,1,2,2]
,排序完成。
这个算法的核心是通过遍历数组,动态调整0、1、2的位置,保证红色、白色、蓝色按照顺序排列。
java 代码:
class Solution {public void sortColors(int[] nums) {int low = 0, mid = 0, high = nums.length - 1;while(mid <= high) {if(nums[mid] == 0) {swap(nums, low, mid);low++;mid++;} else if(nums[mid] == 1) {mid++;} else if(nums[mid] == 2) {swap(nums, mid, high);high--;}}}private void swap(int[] nums, int start, int end) {int temp = nums[start];nums[start] = nums[end];nums[end] = temp;}
}
相关文章:

Leetcode 颜色分类
这个算法采用了荷兰国旗问题(Dutch National Flag Problem)的解法思想,用三个指针将数组中的元素分为三个区域,并且对这些区域进行动态调整,达到排序的目的。 算法思想: 三个指针: low 指针表示…...
ssh连接阿里云长连接
如何让ssh保持连接? 有时候用ssh连接阿里云莫名奇妙断开了。怎么样才能保持连接呢? 修改系统的链接参数: (1)修改/etc/ssh/sshd_config文件,找到 ClientAliveInterval 0和ClientAliveCountMax 3并将注释符号&#x…...
栈的C实现
栈的C实现 栈简介栈的C实现1.栈结构体2.初始化栈3.栈的基本操作 栈简介 栈(Stack)是一种后进先出的数据结构,类似于一个垂直的容器。 栈的特点是后进先出,即最后入栈的元素最先出栈。栈可以用来解决递归问题、实现函数调用、以及…...
【MySQL】入门篇—数据库基础:关系数据库概念
一、背景与重要性 在当今数字化时代,数据的管理和存储变得尤为重要。无论是企业的客户信息、产品数据,还是社交媒体上的用户互动,数据都是推动业务和决策的核心。 关系数据库管理系统(RDBMS)是一种广泛使用的数据管理…...

不到千元的自动猫砂盆是智商税吗?这四大选购技巧不看就亏大了
虽然现在的人都说,猫砂盆等上班一天回来再清理也没有任何关系,但实际上在这一天里,猫咪的粪便已经在猫砂盆里滋生了很多无法察觉的细菌,久而久之就会影响猫咪的健康,导致尿闭,放了一天的便便臭味也让人无法…...

【图论】(二)图论基础与路径问题
图论基础与路径问题 图的构造邻接矩阵邻接表 所有可达路径邻接矩阵存储邻接表存储 字符串接龙有向图的完全可达性 图的构造 这里仅对图论路径问题中图的构造做整理总结归纳,具体详细相关概念请参考代码随想录上的整理总结: 图论理论基础深度优先搜索理…...
Git常用命令(持续更新中)
mkdir one 在当前目录下创建一个名为one的文件夹 cd one 进入one 文件夹 git init 初始化git 仓库 touch README.md 创建一个后缀为.md的新文件README.md git add README.md 将README.md添加到git暂存区 git add * . * 将所有文件添加到暂存区 git add "E:/t…...

什么是PLM系统?PLM系统对制造业起到哪些作用?三品PLM系统对汽车制造业意义
在当今竞争激烈的制造业环境中,企业面临着来自市场、技术、客户需求等多方面的挑战。为了应对这些挑战,许多制造企业纷纷引入产品生命周期管理PLM系统,以实现更高效、更灵活的产品全生命周期管理。PLM系统以其独特的优势,在优化产…...

Pr 视频效果:元数据和时间码刻录
视频效果/视频/元数据和时间码刻录 Video/Metadata & Timecode Burn-in 元数据和时间码刻录 Metadata & Timecode Burn-in效果是一种在视频画面上叠加显示剪辑元数据或时间码的工具。它允许在导出视频时,将需用的元数据信息直接刻录在画面上,方便…...
前端MD5加密
1.导入包 npm install --save ts-md5 2.使用方式 import { Md5 } from ts-md5;//md5加密后的密码 const md5PwdMd5.hashStr("123456").toUpperCase(); 3. Vue解析token中携带的数据 3.1 安装插件 npm install jwt-decode --save 3.2 引入 import {jwtDecode} fro…...

仿IOS桌面悬浮球(支持拖拽、自动吸附、自动改变透明度与点击、兼容PC端与移动端)
使用 pointerdown/pointermove/pointerup 实现仿IOS桌面悬浮球效果,支持拖拽、指定拖拽选对容器,指定拖拽安全区、自动吸附、自动改变透明度与点击,兼容PC端与移动端。 效果展示 https://code.juejin.cn/pen/7423757568268304421 代码实现 …...

智谱开放平台API调用解析
一、什么是智谱AI 智谱AI成立于2019年,由清华大学计算机系知识工程实验室的技术成果转化而来,是一家致力于人工智能技术研发和应用的公司。智谱致力于打造新一代认知智能大模型,专注于做大模型的中国创新。 二、智谱开放平台API调用 官方文…...
Linux中定时删除10天前的日志文件
例如:删除/data/log/目录下所有10天前的.log文件 find /data/log/ -type f -name "*.log" -mtime 10 -exec rm -f {} \;只查看要删除的文件有哪些,不真正删除文件 logfiles$(find /data/log/ -type f -name "*.log" -mtime 10) ec…...
贝壳Android面试题及参考答案
详细说Final关键字 在编程语言中,final关键字具有重要的作用。以下为你详细介绍final关键字: 一、final关键字的主要作用 修饰变量 当final修饰基本数据类型变量时,该变量的值一旦被初始化就不能再被改变。例如:final int num = 10;num = 20; // 这会导致编译错误当final修…...

基于vue的酒店预订管理系统(源码+定制+开发)
博主介绍: ✌我是阿龙,一名专注于Java技术领域的程序员,全网拥有10W粉丝。作为CSDN特邀作者、博客专家、新星计划导师,我在计算机毕业设计开发方面积累了丰富的经验。同时,我也是掘金、华为云、阿里云、InfoQ等平台…...

FreeRTOS——TCB任务控制块、任务句柄、任务栈详解
任务控制块结构体 任务控制块是 FreeRTOS 中用于描述和管理任务的数据结构,包含了任务的状态、优先级、堆栈等信息。 TCB_t的全称为Task Control Block,也就是任务控制块,这个结构体包含了一个任务所有的信息,它的定义以及相关变…...

【STM32单片机_(HAL库)】4-5-2【定时器TIM】【感应开关盖垃圾桶项目】HC-SR04超声波模块实验
1.硬件 STM32单片机最小系统HC-SR04超声波模块 2.软件 hcsr04驱动文件添加main.c程序 #include "sys.h" #include "delay.h" #include "led.h" #include "uart1.h" #include "hcsr04.h"int main(void) {HAL_Init(); …...

安全网络架构
网络安全解决方案是指通过一系列技术和措施来保护网络系统和数据的安全。它涉及多个方面,包括网络设备的防护、数据的加密和备份、安全策略的制定和执行等。以下是一些常见的网络安全解决方案: 防火墙:防火墙是一种硬件或软件设备,…...

【万字长文】Word2Vec计算详解(二)Skip-gram模型
【万字长文】Word2Vec计算详解(二)Skip-gram模型 写在前面 本篇介绍Word2Vec中的第二个模型Skip-gram模型 【万字长文】Word2Vec计算详解(一)CBOW模型 markdown行 9000 【万字长文】Word2Vec计算详解(二)S…...

随机掉落的项目足迹:解决TypeError: Cannot read properties of undefined (reading ‘push‘)报错
问题引入 下面是request.js中请求拦截器相关的代码 但是运行时却出现了报错 问题解决 useRouter() 是 Vue Router 提供的组合式 API,它只能在 Vue 组件的 setup() 函数中有效。如果在其他地方(例如 Axios 的拦截器中)调用它,可…...
谷歌浏览器插件
项目中有时候会用到插件 sync-cookie-extension1.0.0:开发环境同步测试 cookie 至 localhost,便于本地请求服务携带 cookie 参考地址:https://juejin.cn/post/7139354571712757767 里面有源码下载下来,加在到扩展即可使用FeHelp…...

Lombok 的 @Data 注解失效,未生成 getter/setter 方法引发的HTTP 406 错误
HTTP 状态码 406 (Not Acceptable) 和 500 (Internal Server Error) 是两类完全不同的错误,它们的含义、原因和解决方法都有显著区别。以下是详细对比: 1. HTTP 406 (Not Acceptable) 含义: 客户端请求的内容类型与服务器支持的内容类型不匹…...

JavaScript 中的 ES|QL:利用 Apache Arrow 工具
作者:来自 Elastic Jeffrey Rengifo 学习如何将 ES|QL 与 JavaScript 的 Apache Arrow 客户端工具一起使用。 想获得 Elastic 认证吗?了解下一期 Elasticsearch Engineer 培训的时间吧! Elasticsearch 拥有众多新功能,助你为自己…...
服务器硬防的应用场景都有哪些?
服务器硬防是指一种通过硬件设备层面的安全措施来防御服务器系统受到网络攻击的方式,避免服务器受到各种恶意攻击和网络威胁,那么,服务器硬防通常都会应用在哪些场景当中呢? 硬防服务器中一般会配备入侵检测系统和预防系统&#x…...

Nuxt.js 中的路由配置详解
Nuxt.js 通过其内置的路由系统简化了应用的路由配置,使得开发者可以轻松地管理页面导航和 URL 结构。路由配置主要涉及页面组件的组织、动态路由的设置以及路由元信息的配置。 自动路由生成 Nuxt.js 会根据 pages 目录下的文件结构自动生成路由配置。每个文件都会对…...

select、poll、epoll 与 Reactor 模式
在高并发网络编程领域,高效处理大量连接和 I/O 事件是系统性能的关键。select、poll、epoll 作为 I/O 多路复用技术的代表,以及基于它们实现的 Reactor 模式,为开发者提供了强大的工具。本文将深入探讨这些技术的底层原理、优缺点。 一、I…...
【JavaSE】多线程基础学习笔记
多线程基础 -线程相关概念 程序(Program) 是为完成特定任务、用某种语言编写的一组指令的集合简单的说:就是我们写的代码 进程 进程是指运行中的程序,比如我们使用QQ,就启动了一个进程,操作系统就会为该进程分配内存…...

Linux nano命令的基本使用
参考资料 GNU nanoを使いこなすnano基础 目录 一. 简介二. 文件打开2.1 普通方式打开文件2.2 只读方式打开文件 三. 文件查看3.1 打开文件时,显示行号3.2 翻页查看 四. 文件编辑4.1 Ctrl K 复制 和 Ctrl U 粘贴4.2 Alt/Esc U 撤回 五. 文件保存与退出5.1 Ctrl …...
MinIO Docker 部署:仅开放一个端口
MinIO Docker 部署:仅开放一个端口 在实际的服务器部署中,出于安全和管理的考虑,我们可能只能开放一个端口。MinIO 是一个高性能的对象存储服务,支持 Docker 部署,但默认情况下它需要两个端口:一个是 API 端口(用于存储和访问数据),另一个是控制台端口(用于管理界面…...
django blank 与 null的区别
1.blank blank控制表单验证时是否允许字段为空 2.null null控制数据库层面是否为空 但是,要注意以下几点: Django的表单验证与null无关:null参数控制的是数据库层面字段是否可以为NULL,而blank参数控制的是Django表单验证时字…...