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

Leetcode 颜色分类

在这里插入图片描述
这个算法采用了荷兰国旗问题(Dutch National Flag Problem)的解法思想,用三个指针将数组中的元素分为三个区域,并且对这些区域进行动态调整,达到排序的目的。

算法思想:

  1. 三个指针

    • low 指针表示当前0应该存放的区域的边界。
    • mid 指针用来遍历数组,每次检查当前位置的元素。
    • high 指针表示当前2应该存放的区域的边界。
  2. 算法步骤

    • 开始时,lowmid 都指向数组的开头,high 指向数组的末尾。
    • 遍历数组,当 mid 小于等于 high 时:
      • 如果 nums[mid] == 0,表示当前元素是红色(0),应该放到数组的前面,所以与 low 交换,lowmid 同时右移一位。
      • 如果 nums[mid] == 1,表示当前元素是白色(1),不需要移动,mid 右移一位。
      • 如果 nums[mid] == 2,表示当前元素是蓝色(2),应该放到数组的末尾,所以与 high 交换,并将 high 左移一位,而 mid 不动,等待交换后的元素检查。
  3. 循环结束条件

    • 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]lowmid 右移,数组不变。
  • 持续遍历并根据上述逻辑调整,最终数组为 [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 颜色分类

这个算法采用了荷兰国旗问题&#xff08;Dutch National Flag Problem&#xff09;的解法思想&#xff0c;用三个指针将数组中的元素分为三个区域&#xff0c;并且对这些区域进行动态调整&#xff0c;达到排序的目的。 算法思想&#xff1a; 三个指针&#xff1a; low 指针表示…...

ssh连接阿里云长连接

如何让ssh保持连接&#xff1f; 有时候用ssh连接阿里云莫名奇妙断开了。怎么样才能保持连接呢&#xff1f; 修改系统的链接参数: &#xff08;1&#xff09;修改/etc/ssh/sshd_config文件&#xff0c;找到 ClientAliveInterval 0和ClientAliveCountMax 3并将注释符号&#x…...

栈的C实现

栈的C实现 栈简介栈的C实现1.栈结构体2.初始化栈3.栈的基本操作 栈简介 栈&#xff08;Stack&#xff09;是一种后进先出的数据结构&#xff0c;类似于一个垂直的容器。 栈的特点是后进先出&#xff0c;即最后入栈的元素最先出栈。栈可以用来解决递归问题、实现函数调用、以及…...

【MySQL】入门篇—数据库基础:关系数据库概念

一、背景与重要性 在当今数字化时代&#xff0c;数据的管理和存储变得尤为重要。无论是企业的客户信息、产品数据&#xff0c;还是社交媒体上的用户互动&#xff0c;数据都是推动业务和决策的核心。 关系数据库管理系统&#xff08;RDBMS&#xff09;是一种广泛使用的数据管理…...

不到千元的自动猫砂盆是智商税吗?这四大选购技巧不看就亏大了

虽然现在的人都说&#xff0c;猫砂盆等上班一天回来再清理也没有任何关系&#xff0c;但实际上在这一天里&#xff0c;猫咪的粪便已经在猫砂盆里滋生了很多无法察觉的细菌&#xff0c;久而久之就会影响猫咪的健康&#xff0c;导致尿闭&#xff0c;放了一天的便便臭味也让人无法…...

【图论】(二)图论基础与路径问题

图论基础与路径问题 图的构造邻接矩阵邻接表 所有可达路径邻接矩阵存储邻接表存储 字符串接龙有向图的完全可达性 图的构造 这里仅对图论路径问题中图的构造做整理总结归纳&#xff0c;具体详细相关概念请参考代码随想录上的整理总结&#xff1a; 图论理论基础深度优先搜索理…...

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系统对汽车制造业意义

在当今竞争激烈的制造业环境中&#xff0c;企业面临着来自市场、技术、客户需求等多方面的挑战。为了应对这些挑战&#xff0c;许多制造企业纷纷引入产品生命周期管理PLM系统&#xff0c;以实现更高效、更灵活的产品全生命周期管理。PLM系统以其独特的优势&#xff0c;在优化产…...

Pr 视频效果:元数据和时间码刻录

视频效果/视频/元数据和时间码刻录 Video/Metadata & Timecode Burn-in 元数据和时间码刻录 Metadata & Timecode Burn-in效果是一种在视频画面上叠加显示剪辑元数据或时间码的工具。它允许在导出视频时&#xff0c;将需用的元数据信息直接刻录在画面上&#xff0c;方便…...

前端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桌面悬浮球效果&#xff0c;支持拖拽、指定拖拽选对容器&#xff0c;指定拖拽安全区、自动吸附、自动改变透明度与点击&#xff0c;兼容PC端与移动端。 效果展示 https://code.juejin.cn/pen/7423757568268304421 代码实现 …...

智谱开放平台API调用解析

一、什么是智谱AI 智谱AI成立于2019年&#xff0c;由‌清华大学计算机系知识工程实验室的技术成果转化而来&#xff0c;是一家致力于人工智能技术研发和应用的公司。智谱致力于打造新一代认知智能大模型&#xff0c;专注于做大模型的中国创新。 二、智谱开放平台API调用 官方文…...

Linux中定时删除10天前的日志文件

例如&#xff1a;删除/data/log/目录下所有10天前的.log文件 find /data/log/ -type f -name "*.log" -mtime 10 -exec rm -f {} \;只查看要删除的文件有哪些&#xff0c;不真正删除文件 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的酒店预订管理系统(源码+定制+开发)

博主介绍&#xff1a; ✌我是阿龙&#xff0c;一名专注于Java技术领域的程序员&#xff0c;全网拥有10W粉丝。作为CSDN特邀作者、博客专家、新星计划导师&#xff0c;我在计算机毕业设计开发方面积累了丰富的经验。同时&#xff0c;我也是掘金、华为云、阿里云、InfoQ等平台…...

FreeRTOS——TCB任务控制块、任务句柄、任务栈详解

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

【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(); …...

安全网络架构

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

【万字长文】Word2Vec计算详解(二)Skip-gram模型

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

随机掉落的项目足迹:解决TypeError: Cannot read properties of undefined (reading ‘push‘)报错

问题引入 下面是request.js中请求拦截器相关的代码 但是运行时却出现了报错 问题解决 useRouter() 是 Vue Router 提供的组合式 API&#xff0c;它只能在 Vue 组件的 setup() 函数中有效。如果在其他地方&#xff08;例如 Axios 的拦截器中&#xff09;调用它&#xff0c;可…...

springboot 百货中心供应链管理系统小程序

一、前言 随着我国经济迅速发展&#xff0c;人们对手机的需求越来越大&#xff0c;各种手机软件也都在被广泛应用&#xff0c;但是对于手机进行数据信息管理&#xff0c;对于手机的各种软件也是备受用户的喜爱&#xff0c;百货中心供应链管理系统被用户普遍使用&#xff0c;为方…...

Redis相关知识总结(缓存雪崩,缓存穿透,缓存击穿,Redis实现分布式锁,如何保持数据库和缓存一致)

文章目录 1.什么是Redis&#xff1f;2.为什么要使用redis作为mysql的缓存&#xff1f;3.什么是缓存雪崩、缓存穿透、缓存击穿&#xff1f;3.1缓存雪崩3.1.1 大量缓存同时过期3.1.2 Redis宕机 3.2 缓存击穿3.3 缓存穿透3.4 总结 4. 数据库和缓存如何保持一致性5. Redis实现分布式…...

多模态商品数据接口:融合图像、语音与文字的下一代商品详情体验

一、多模态商品数据接口的技术架构 &#xff08;一&#xff09;多模态数据融合引擎 跨模态语义对齐 通过Transformer架构实现图像、语音、文字的语义关联。例如&#xff0c;当用户上传一张“蓝色连衣裙”的图片时&#xff0c;接口可自动提取图像中的颜色&#xff08;RGB值&…...

将对透视变换后的图像使用Otsu进行阈值化,来分离黑色和白色像素。这句话中的Otsu是什么意思?

Otsu 是一种自动阈值化方法&#xff0c;用于将图像分割为前景和背景。它通过最小化图像的类内方差或等价地最大化类间方差来选择最佳阈值。这种方法特别适用于图像的二值化处理&#xff0c;能够自动确定一个阈值&#xff0c;将图像中的像素分为黑色和白色两类。 Otsu 方法的原…...

鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个生活电费的缴纳和查询小程序

一、项目初始化与配置 1. 创建项目 ohpm init harmony/utility-payment-app 2. 配置权限 // module.json5 {"requestPermissions": [{"name": "ohos.permission.INTERNET"},{"name": "ohos.permission.GET_NETWORK_INFO"…...

MySQL中【正则表达式】用法

MySQL 中正则表达式通过 REGEXP 或 RLIKE 操作符实现&#xff08;两者等价&#xff09;&#xff0c;用于在 WHERE 子句中进行复杂的字符串模式匹配。以下是核心用法和示例&#xff1a; 一、基础语法 SELECT column_name FROM table_name WHERE column_name REGEXP pattern; …...

Go 并发编程基础:通道(Channel)的使用

在 Go 中&#xff0c;Channel 是 Goroutine 之间通信的核心机制。它提供了一个线程安全的通信方式&#xff0c;用于在多个 Goroutine 之间传递数据&#xff0c;从而实现高效的并发编程。 本章将介绍 Channel 的基本概念、用法、缓冲、关闭机制以及 select 的使用。 一、Channel…...

【p2p、分布式,区块链笔记 MESH】Bluetooth蓝牙通信 BLE Mesh协议的拓扑结构 定向转发机制

目录 节点的功能承载层&#xff08;GATT/Adv&#xff09;局限性&#xff1a; 拓扑关系定向转发机制定向转发意义 CG 节点的功能 节点的功能由节点支持的特性和功能决定。所有节点都能够发送和接收网格消息。节点还可以选择支持一个或多个附加功能&#xff0c;如 Configuration …...

libfmt: 现代C++的格式化工具库介绍与酷炫功能

libfmt: 现代C的格式化工具库介绍与酷炫功能 libfmt 是一个开源的C格式化库&#xff0c;提供了高效、安全的文本格式化功能&#xff0c;是C20中引入的std::format的基础实现。它比传统的printf和iostream更安全、更灵活、性能更好。 基本介绍 主要特点 类型安全&#xff1a…...

十九、【用户管理与权限 - 篇一】后端基础:用户列表与角色模型的初步构建

【用户管理与权限 - 篇一】后端基础:用户列表与角色模型的初步构建 前言准备工作第一部分:回顾 Django 内置的 `User` 模型第二部分:设计并创建 `Role` 和 `UserProfile` 模型第三部分:创建 Serializers第四部分:创建 ViewSets第五部分:注册 API 路由第六部分:后端初步测…...