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

【算法系列】荷兰国旗问题:三指针法原地排序

一、题目(leetcode75 颜色分类 --三分数组)


二、思路

算法核心:三指针分治策略  
该问题被称为“荷兰国旗问题”(Dutch National Flag Problem),由计算机科学家Edsger Dijkstra提出。其核心思想是通过三个指针将数组划分为三个区域,逐步将元素归位。

指针定义与规则  
1. 指针分工  
left:标记`0`的右边界(初始指向头部)  
i:当前遍历位置(初始指向头部)  
right:标记`2`的左边界(初始指向尾部)  

2. 遍历规则


三、代码

class Solution {
public:void sortColors(vector<int>& nums) {int left=-1,right=nums.size(),i=0;while(i<right){if(nums[i]==0)swap(nums[++left],nums[i++]);else if(nums[i]==1)++i;elseswap(nums[i],nums[--right]);}}
};

复杂度与适用场景  

时间复杂度:O(n),线性遍历。  
空间复杂度:O(1),仅使用常数指针。  
适用场景:元素种类有限(如3种)的快速原地排序,例如图像处理中的像素值排序、分类统计等。  

总结  

三指针法通过巧妙的分区策略,将荷兰国旗问题的时间复杂度优化到极致。该算法不仅是一道经典面试题,更体现了分治思想在实际工程中的应用价值。掌握这一方法,可轻松应对类似的多分类排序问题。

相关文章:

【算法系列】荷兰国旗问题:三指针法原地排序

一、题目(leetcode75 颜色分类 --三分数组) 二、思路 算法核心&#xff1a;三指针分治策略 该问题被称为“荷兰国旗问题”&#xff08;Dutch National Flag Problem&#xff09;&#xff0c;由计算机科学家Edsger Dijkstra提出。其核心思想是通过三个指针将数组划分为三个区…...

DeepSeek R1本地+私有云版医疗AI部署开发成功案例技术剖析

1. 引言 1.1 研究背景与意义 随着科技的飞速发展,人工智能(AI)在医疗领域的应用正逐渐成为推动医疗行业变革的重要力量。近年来,医疗 AI 取得了显著的进展,从疾病诊断、药物研发到医疗管理等各个环节,AI 技术都展现出了巨大的潜力。它能够处理和分析海量的医疗数据,为…...

ARM64 Trust Firmware [五]

本章介绍 ATF 中的 Runtime Service 是如何定义和被调用的。 要了解 SMC&#xff0c;必须从 SMC 指令本身开始&#xff0c;其指令如下图&#xff1a; 指令格式为&#xff1a;SMC #<imm>&#xff0c;从官方文档了解到该指令只能在 EL1 以及更高的异常等级上调用&#xff…...

rkipc main.c 中 rk_param_init函数分析

rk_param_init函数 这个函数是用来读取配置文件进行参数配置 这个函数在 luckfox-pico/project/app/rk_smart_door/smart_door/common/uvc/param/param.c 中 这个函数在main函数中被调用 //通过-c 配置文件路径 把配置文件传进来 case c:rkipc_ini_path_ optarg;//调用&am…...

正确清理C盘空间

一.系统清理 正确清理C盘空间主要是删除不需要的文件和应用程序&#xff0c;以释放磁盘空间。以下是一些常用的方法&#xff1a; 删除临时文件&#xff1a;在Windows搜索框中输入“%temp%”&#xff0c;打开临时文件夹&#xff0c;将其中的文件全部删除。 清理回收站&#xf…...

http代理IP怎么实现?如何解决代理IP访问不了问题?

HTTP代理是一种网络服务&#xff0c;它充当客户端和目标服务器之间的中介。当客户端发送请求时&#xff0c;请求首先发送到代理服务器&#xff0c;然后由代理服务器转发到目标服务器。同样&#xff0c;目标服务器的响应也会先发送到代理服务器&#xff0c;再由代理服务器返回给…...

【Gin-Web】Bluebell社区项目梳理5:投票功能分析与实现

本文目录 一、投票功能投票流程实现代码redis投票 一、投票功能 投票流程 首先我们要明确&#xff0c;就是 谁&#xff08;哪个用户&#xff1a;userID&#xff09; 给 哪个帖子&#xff08;postID&#xff09; 投了 什么票&#xff08;赞成票or反对票&#xff09;。 赞成票…...

多人协同创作gitea

多人协同创作gitea 在多台设备上协同使用Gitea&#xff0c;主要是通过网络访问Gitea服务器上的仓库来进行代码管理和协作。以下是一些关键步骤和建议&#xff0c;帮助你在多台设备上高效地使用Gitea进行协作&#xff1a; 1. 确保Gitea服务可访问 首先&#xff0c;你需要确保…...

Java 大视界 -- Java 大数据未来十年的技术蓝图与发展愿景(95)

&#x1f496;亲爱的朋友们&#xff0c;热烈欢迎来到 青云交的博客&#xff01;能与诸位在此相逢&#xff0c;我倍感荣幸。在这飞速更迭的时代&#xff0c;我们都渴望一方心灵净土&#xff0c;而 我的博客 正是这样温暖的所在。这里为你呈上趣味与实用兼具的知识&#xff0c;也…...

idea连接gitee完整教程

文章目录 idea连接gitee(使用idea远程兼容gitee) 使用idea远程兼容gitee并反向创建仓库和分支...

问卷数据分析|SPSS实操之相关分析

皮尔逊还是斯皮尔曼的选取主要看数据的分布 当数据满足正态分布且具有线性关系时&#xff0c;用皮尔逊相关系数 当有一个不满住时&#xff0c;用斯皮尔曼相关系数 1. 选择分析--相关--双变量 2. 将Z1-Y2加入到变量中&#xff0c;选择皮尔逊 3. 此处为结果&#xff0c;可看我案…...

汽配出库软件助力企业数字化转型,佳易王汽配出入库管理系统操作教程

一、概述 本实例以佳易王汽配出入库管理系统V17.1版本为例说明&#xff0c;其他版本可参考本实例。试用版软件资源可到文章最后了解&#xff0c;下载的文件为压缩包文件&#xff0c;请使用免费版的解压工具解压即可试用。 软件特点&#xff1a; 1、软件为绿色免安装版&#…...

二叉树(中等题)

1、先序&#xff0c;中序遍历确定二叉树 105 方法一、 前提 ① 必须不能有重复元素② 只有先序&#xff0b;中序和后序&#xff0b;中序才能实现唯一树 思考要点&#xff1a; 不要想着用for循环&#xff0c;递归一定更好解决输入是vector&#xff0c;递归就得考虑传入索…...

Versal - 基础6(Linux 开发 AIE-ML + 自动化脚本解析)

目录 1. 简介 2. 步骤解析 2.1 概览 2.1.1 步骤依赖关系 2.1.2 总目录结构 2.2 Vitis XPFM 2.2.1 Dir 2.2.2 Makefile 2.2.3 vitis_pfm.py 2.3 Kernels 2.3.1 Dir 2.3.2 Makefile 2.3.3 config 文件 2.4 AIE_app 2.4.1 Dir 2.4.2 Makefile 2.4.3 aie 要点 2.…...

什么是矩阵账号?如何高效运营tiktok矩阵账号

‍‌​​‌‌​‌​‍‌​​​‌‌​​‍‌​​​‌​‌​‍‌​​‌​​‌​‍‌​‌‌​‌‌‌‍‌​‌​‌​​​‍‌​​‌​‌‌​‍‌​​​​‌‌​‍‌​‌​​‌‌‌‍‌​​‌‌​‌​‍‌​‌​​‌‌‌‍‌​‌‌‌​​‌‍‌‌​​‌‌‌​‍‌‌​​‌‌​​‍‌…...

tortoiseSVN 如何克隆项目到本地

导入项目成功&#xff0c;如下图&#xff1a;...

趣解PostGet请求的原理、应用场景及区别

趣解Post&Get请求的原理、应用场景及区别 POST 和 GET 的「身份之谜」&#xff1a;快递员与侦探的终极对决 一、角色设定&#xff1a;快递员&#xff08;POST&#xff09; vs 侦探&#xff08;GET&#xff09; GET&#xff08;侦探&#xff09;&#xff1a; 任务&#xff…...

在PHP Web开发中,实现异步处理有几种常见方式的优缺点,以及最佳实践推荐方法

1. 消息队列 使用消息队列&#xff08;如RabbitMQ、Beanstalkd、Redis&#xff09;将任务放入队列&#xff0c;由后台进程异步处理。 优点&#xff1a; 任务持久化&#xff0c;系统崩溃后任务不丢失。 支持分布式处理&#xff0c;扩展性强。 实现步骤&#xff1a; 安装消息…...

深入解析过滤器模式:数据筛选与处理的高效工具

过滤器模式&#xff1a;数据筛选与处理的高效工具 在软件开发的复杂领域中&#xff0c;数据的筛选与处理是常见的任务。过滤器模式作为一种实用的设计模式&#xff0c;为解决这类问题提供了有效的解决方案。它允许开发者根据不同的标准对一组对象进行过滤操作&#xff0c;从而…...

DeepSeek R1/V3满血版——在线体验与API调用

前言&#xff1a;在人工智能的大模型发展进程中&#xff0c;每一次新模型的亮相都宛如一颗投入湖面的石子&#xff0c;激起层层波澜。如今&#xff0c;DeepSeek R1/V3 满血版强势登场&#xff0c;为大模型应用领域带来了全新的活力与变革。 本文不但介绍在线体验 DeepSeek R1/…...

【Linux】shell脚本忽略错误继续执行

在 shell 脚本中&#xff0c;可以使用 set -e 命令来设置脚本在遇到错误时退出执行。如果你希望脚本忽略错误并继续执行&#xff0c;可以在脚本开头添加 set e 命令来取消该设置。 举例1 #!/bin/bash# 取消 set -e 的设置 set e# 执行命令&#xff0c;并忽略错误 rm somefile…...

React Native 开发环境搭建(全平台详解)

React Native 开发环境搭建&#xff08;全平台详解&#xff09; 在开始使用 React Native 开发移动应用之前&#xff0c;正确设置开发环境是至关重要的一步。本文将为你提供一份全面的指南&#xff0c;涵盖 macOS 和 Windows 平台的配置步骤&#xff0c;如何在 Android 和 iOS…...

MODBUS TCP转CANopen 技术赋能高效协同作业

在现代工业自动化领域&#xff0c;MODBUS TCP和CANopen两种通讯协议因其稳定性和高效性被广泛应用于各种设备和系统中。而随着科技的不断进步&#xff0c;这两种通讯协议也正在被逐步融合&#xff0c;形成了一种新型的通讯方式——开疆智能MODBUS TCP转CANopen网关KJ-TCPC-CANP…...

涂鸦T5AI手搓语音、emoji、otto机器人从入门到实战

“&#x1f916;手搓TuyaAI语音指令 &#x1f60d;秒变表情包大师&#xff0c;让萌系Otto机器人&#x1f525;玩出智能新花样&#xff01;开整&#xff01;” &#x1f916; Otto机器人 → 直接点明主体 手搓TuyaAI语音 → 强调 自主编程/自定义 语音控制&#xff08;TuyaAI…...

DingDing机器人群消息推送

文章目录 1 新建机器人2 API文档说明3 代码编写 1 新建机器人 点击群设置 下滑到群管理的机器人&#xff0c;点击进入 添加机器人 选择自定义Webhook服务 点击添加 设置安全设置&#xff0c;详见说明文档 成功后&#xff0c;记录Webhook 2 API文档说明 点击设置说明 查看自…...

从物理机到云原生:全面解析计算虚拟化技术的演进与应用

前言&#xff1a;我的虚拟化技术探索之旅 我最早接触"虚拟机"的概念是从Java开始的——JVM&#xff08;Java Virtual Machine&#xff09;让"一次编写&#xff0c;到处运行"成为可能。这个软件层面的虚拟化让我着迷&#xff0c;但直到后来接触VMware和Doc…...

大模型——基于Docker+DeepSeek+Dify :搭建企业级本地私有化知识库超详细教程

基于Docker+DeepSeek+Dify :搭建企业级本地私有化知识库超详细教程 下载安装Docker Docker官网:https://www.docker.com/ 自定义Docker安装路径 Docker默认安装在C盘,大小大概2.9G,做这行最忌讳的就是安装软件全装C盘,所以我调整了下安装路径。 新建安装目录:E:\MyS…...

MeshGPT 笔记

[2311.15475] MeshGPT: Generating Triangle Meshes with Decoder-Only Transformers https://library.scholarcy.com/try 真正意义上的AI生成三维模型MESHGPT来袭&#xff01;_哔哩哔哩_bilibili GitHub - lucidrains/meshgpt-pytorch: Implementation of MeshGPT, SOTA Me…...

Selenium 查找页面元素的方式

Selenium 查找页面元素的方式 Selenium 提供了多种方法来查找网页中的元素&#xff0c;以下是主要的定位方式&#xff1a; 基本定位方式 通过ID定位 driver.find_element(By.ID, "element_id")通过Name定位 driver.find_element(By.NAME, "element_name"…...

更新 Docker 容器中的某一个文件

&#x1f504; 如何更新 Docker 容器中的某一个文件 以下是几种在 Docker 中更新单个文件的常用方法&#xff0c;适用于不同场景。 ✅ 方法一&#xff1a;使用 docker cp 拷贝文件到容器中&#xff08;最简单&#xff09; &#x1f9f0; 命令格式&#xff1a; docker cp <…...