当前位置: 首页 > 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/…...

通过Wrangler CLI在worker中创建数据库和表

官方使用文档&#xff1a;Getting started Cloudflare D1 docs 创建数据库 在命令行中执行完成之后&#xff0c;会在本地和远程创建数据库&#xff1a; npx wranglerlatest d1 create prod-d1-tutorial 在cf中就可以看到数据库&#xff1a; 现在&#xff0c;您的Cloudfla…...

linux 错误码总结

1,错误码的概念与作用 在Linux系统中,错误码是系统调用或库函数在执行失败时返回的特定数值,用于指示具体的错误类型。这些错误码通过全局变量errno来存储和传递,errno由操作系统维护,保存最近一次发生的错误信息。值得注意的是,errno的值在每次系统调用或函数调用失败时…...

Mac软件卸载指南,简单易懂!

刚和Adobe分手&#xff0c;它却总在Library里给你写"回忆录"&#xff1f;卸载的Final Cut Pro像电子幽灵般阴魂不散&#xff1f;总是会有残留文件&#xff0c;别慌&#xff01;这份Mac软件卸载指南&#xff0c;将用最硬核的方式教你"数字分手术"&#xff0…...

dify打造数据可视化图表

一、概述 在日常工作和学习中&#xff0c;我们经常需要和数据打交道。无论是分析报告、项目展示&#xff0c;还是简单的数据洞察&#xff0c;一个清晰直观的图表&#xff0c;往往能胜过千言万语。 一款能让数据可视化变得超级简单的 MCP Server&#xff0c;由蚂蚁集团 AntV 团队…...

深度学习习题2

1.如果增加神经网络的宽度&#xff0c;精确度会增加到一个特定阈值后&#xff0c;便开始降低。造成这一现象的可能原因是什么&#xff1f; A、即使增加卷积核的数量&#xff0c;只有少部分的核会被用作预测 B、当卷积核数量增加时&#xff0c;神经网络的预测能力会降低 C、当卷…...

服务器--宝塔命令

一、宝塔面板安装命令 ⚠️ 必须使用 root 用户 或 sudo 权限执行&#xff01; sudo su - 1. CentOS 系统&#xff1a; yum install -y wget && wget -O install.sh http://download.bt.cn/install/install_6.0.sh && sh install.sh2. Ubuntu / Debian 系统…...

代码随想录刷题day30

1、零钱兑换II 给你一个整数数组 coins 表示不同面额的硬币&#xff0c;另给一个整数 amount 表示总金额。 请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额&#xff0c;返回 0 。 假设每一种面额的硬币有无限个。 题目数据保证结果符合 32 位带…...

uniapp 开发ios, xcode 提交app store connect 和 testflight内测

uniapp 中配置 配置manifest 文档&#xff1a;manifest.json 应用配置 | uni-app官网 hbuilderx中本地打包 下载IOS最新SDK 开发环境 | uni小程序SDK hbulderx 版本号&#xff1a;4.66 对应的sdk版本 4.66 两者必须一致 本地打包的资源导入到SDK 导入资源 | uni小程序SDK …...

C# 表达式和运算符(求值顺序)

求值顺序 表达式可以由许多嵌套的子表达式构成。子表达式的求值顺序可以使表达式的最终值发生 变化。 例如&#xff0c;已知表达式3*52&#xff0c;依照子表达式的求值顺序&#xff0c;有两种可能的结果&#xff0c;如图9-3所示。 如果乘法先执行&#xff0c;结果是17。如果5…...

NPOI操作EXCEL文件 ——CAD C# 二次开发

缺点:dll.版本容易加载错误。CAD加载插件时&#xff0c;没有加载所有类库。插件运行过程中用到某个类库&#xff0c;会从CAD的安装目录找&#xff0c;找不到就报错了。 【方案2】让CAD在加载过程中把类库加载到内存 【方案3】是发现缺少了哪个库&#xff0c;就用插件程序加载进…...