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

【Java 优选算法】分治 - 快速排序

欢迎关注个人主页:逸狼


创造不易,可以点点赞吗~

如有错误,欢迎指出~



分治算法就是将一个问题划分为多个相同类型的子问题,解决这些子问题即解决该类问题 

颜色分类

题目链接

解法

利用三指针, i, left, right,将数组分为4个区间,如下图

三个指针的起始位置分别是

  1. left = -1 ,
  2. right = nums.length ,
  3. i =0 
  • 当nums[i]==0时,swap(nums[++left], nums[i++])
  • 当nums[i]==1时,i++;
  • 当nums[i]==2时,swap(nums[--right], nums[i]),记住此时的i还是未遍历元素,不能++

代码

class Solution {public void sortColors(int[] nums) {int n = nums.length;int i = 0, left = -1, right = n;while(i < right){if(nums[i] == 0) swap(nums, i++, ++left);else if(nums[i] == 1) i++;else swap(nums, --right, i);}}public void swap(int[] nums, int i, int j){int tmp = nums[i];nums[i] = nums[j];nums[j] = tmp;}
}

排序数组

题目链接

解法

利用上一题的"数组分三块"的思想实现快排.

随机取数组的一个key作为基准值,以此将数组分为三部分,即小于key,等于key,和大于key三部分.

此时只有小于key和大于key的部分是乱序的,后面使用递归将这两部分也排成有序部分.

优化: 取随机数r,可以计算基准值: key=num[r % (right - left + 1) + left]

代码

class Solution {public int[] sortArray(int[] nums) {qsort(nums, 0, nums.length - 1);return nums;}public void qsort(int[] nums, int l, int r){if(l >= r) return;//数组分三块int key = nums[new Random().nextInt(r - l + 1)+ l];int left = l - 1, right = r + 1, i = l;while(i < right){if(nums[i] < key) swap(nums, ++left, i++);else if(nums[i] == key) i++;else swap(nums, --right, i);}//[l,left],[left +1, right - 1][right, r]qsort(nums,l, left);qsort(nums,right,r);}public void swap(int[] nums, int i, int j){int tmp = nums[i];nums[i] = nums[j];nums[j] = tmp;}
}

数组中的第K个最大元素

题目链接

类似问题还有 前k大,前k小,第k大,第k小 问题 

解法

解法一: 使用堆,使用小根堆

解法二: 数组分三块 + 随机选择基准元素

题目要求的是取出第k大的元素,我们记为t 根据数组分三块思想将数组根据基准值key分为三部分,每个部分元素个数是a,b,c, 分下面三种情况

  1. 当c >= k时,说明 t 一定在区间[right, r]
  2. 当b+c >= k时,说明 t 一定是key
  3. 当b+c+a >= k 时,说明 t在区间[l, left]

代码

class Solution {public void swap(int[] nums, int i, int j){int t = nums[i];nums[i]= nums[j];nums[j] = t;}public int findKthLargest(int[] nums, int k) {return qsort(nums, 0, nums.length-1, k);}public int qsort(int[] nums,int l, int r, int k){if(l >= r) return nums[l];int left =l-1, i = l, right =r + 1, key = nums[new Random().nextInt(r - l + 1) + l];while(i < right){if(nums[i] < key) swap(nums, ++left, i++);else if(nums[i] == key) i++;else swap(nums, --right, i);}//计算每个区间的长度int a = left - l + 1, b = right - left - 1, c = r - right + 1;if(c >= k) return qsort(nums, right, r, k);else if( b + c >= k) return key;else return qsort(nums, l, left, k - b - c);}
}

库存管理|||

题目链接

解法

解法一: 排序,N*logN先将数组排序,再从小到大选择符合要求的元素

解法二:堆, N*log k ,建立一个大根堆

解法三: 快速选择算法,N, 随机选择基准元素+数组分三块,

下面展示解法三: 与上一题类似

代码

class Solution {public void swap(int[] nums, int i, int j){int tmp = nums[i];nums[i] = nums[j];nums[j] = tmp;}public int[] inventoryManagement(int[] stock, int cnt) {qsort(stock, 0, stock.length-1, cnt);int[] ret = new int[cnt];for(int i = 0; i < cnt; i++){ret[i] = stock[i];}return ret;}public void qsort(int[] nums, int l, int r, int k){if(l >= r) return;int left = l - 1, right = r + 1, i = l, key = nums[new Random().nextInt(r - l + 1) + l];while(i < right){if(nums[i] < key) swap(nums, ++left, i++);else if(nums[i] == key) i++;else swap(nums, --right, i);}int a = left - l + 1, b = right - left - 1, c = r - right + 1;if(a > k) qsort(nums, l, left, k);else if(a + b >= k) return;else qsort(nums, right, r, k - a - b);}
}

相关文章:

【Java 优选算法】分治 - 快速排序

欢迎关注个人主页&#xff1a;逸狼 创造不易&#xff0c;可以点点赞吗~ 如有错误&#xff0c;欢迎指出~ 分治算法就是将一个问题划分为多个相同类型的子问题,解决这些子问题即解决该类问题 颜色分类 题目链接 解法 利用三指针, i, left, right,将数组分为4个区间,如下图 …...

Kafka相关的面试题

以下是150道Kafka相关的面试题及简洁回答&#xff1a; Kafka基础概念 1. 什么是Kafka&#xff1f; Kafka是一个分布式、可扩展、容错的发布-订阅消息系统&#xff0c;最初由LinkedIn开发&#xff0c;现为Apache项目。它适用于高吞吐量的场景&#xff0c;如大数据处理和实时数据…...

Java基础面经

Java 基础 面试官&#xff1a;重写与重载的区别&#xff1f; 重载&#xff1a;发生在同一个类中&#xff0c;若多个方法之间方法名相同、参数列表不同&#xff0c;则它们构成重载的关系。重载与方法的返回值以及访问修饰符无关&#xff0c;即重载的方法不能根据返回类型进行…...

Let’s Build AI- 实用AI导航网站

Let’s Build AI Let’s Build AI是一个在线实用AI导航网站&#xff0c;由社区驱动的平台&#xff0c;致力于为 AI 爱好者和开发人员共享资源、工具和知识等等&#xff0c;通过GitHub编辑内容更新&#xff0c;目前包括数据库、模型、开发者工具、ChatGPT提示、图像生成、模型开…...

Spring Boot集成EasyExcel

1. 初始化Spring Boot项目 首先&#xff0c;使用Spring Initializr&#xff08;https://start.spring.io/&#xff09;生成一个基本的Spring Boot项目。选择以下依赖项&#xff1a; Spring WebLombok (用于减少样板代码)SLF4J (用于日志记录) 2. 添加依赖 在你的pom.xml文件…...

2024年12月CCF-GESP编程能力等级认证C++编程六级真题解析

CCF-GESP C++六级真题难度与考察范围深度解析 考试定位与整体难度 CCF-GESP C++六级认证属于高阶编程能力考核,难度显著高于五级,接近信息学竞赛提高组水平,重点考察复杂算法设计、面向对象编程(OOP)深度应用及高级数据结构实现能力。试题要求考生具备将数学建模与算法优化…...

网络VLAN技术详解:原理、类型与实战配置

网络VLAN技术详解&#xff1a;原理、类型与实战配置 1. 什么是VLAN&#xff1f; VLAN&#xff08;Virtual Local Area Network&#xff0c;虚拟局域网&#xff09; 是一种通过逻辑划分而非物理连接隔离网络设备的技术。它允许管理员将同一物理网络中的设备划分为多个独立的广播…...

深入探讨RAID 5的性能与容错能力:实验与分析(磁盘阵列)

前言—— 本实验旨在探讨 RAID 5 的性能和容错能力。通过创建 RAID 5 阵列并进行一系列读写性能测试及故障模拟&#xff0c;我们将观察 RAID 5 在数据冗余和故障恢复方面的表现&#xff0c;以验证其在实际应用中的可靠性和效率。 首先说明&#xff1a;最少三块硬盘, 使用 4 块…...

如何让ai问答机器人通人性?

领域专用的问答机器人&#xff0c;数据是灵魂。通用模型的问题在于&#xff0c;它们虽然知识广博&#xff0c;但对特定领域的深度理解不足。解决这个问题的第一步&#xff0c;就是构建一个高质量的领域知识库。 数据要精准且全面 想让机器人真正“懂”一个领域&#xff0c;数…...

最新版Chrome浏览器加载ActiveX控件技术--allWebPlugin中间件一键部署浏览器扩展

allWebPlugin简介 allWebPlugin中间件是一款为用户提供安全、可靠、便捷的浏览器插件服务的中间件产品&#xff0c;致力于将浏览器插件重新应用到所有浏览器。它将现有ActiveX控件直接嵌入浏览器&#xff0c;实现插件加载、界面显示、接口调用、事件回调等。支持Chrome、Firefo…...

重生之我在学Vue--第11天 Vue 3 高级特性

重生之我在学Vue–第11天 Vue 3 高级特性 文章目录 重生之我在学Vue--第11天 Vue 3 高级特性前言一、Teleport&#xff1a;打破组件层级的瞬移术1. 什么是Teleport&#xff1f;2. 核心用法3. 实战技巧 二、Suspense&#xff1a;异步组件的优雅过渡1. 为什么需要Suspense&#x…...

汽车无钥匙启动系统不使用传统机械钥匙启动汽车

汽车无钥匙启动系统 定义 汽车无钥匙启动系统&#xff08;Keyless Start System&#xff09;&#xff0c;启动车辆时不用掏拧钥匙&#xff0c;只需把钥匙放在包内或口袋里&#xff0c;按下车内按键或拧动导板即可使发动机点火。它无需插入钥匙&#xff0c;通过点按按键或旋转…...

平安养老险深圳分公司积极开展2025年“3·15”金融消费者权益保护教育宣传活动

为深刻把握金融工作的政治性、人民性&#xff0c;帮助社会公众增强维护自身合法权益的意识和能力&#xff0c;平安养老险深圳分公司在2025年3月7日至3月15日期间&#xff0c;以“保障金融权益&#xff0c;助力美好生活”为口号&#xff0c;聚焦“维护权益”主题&#xff0c;全面…...

python 实现 A* 算法

A*算法是一种广泛使用的路径搜索算法&#xff0c;结合了启发式搜索和Dijkstra算法的优点。它通过评估每个节点的代价函数 ( f(n) g(n) h(n) ) 来选择最优路径&#xff0c;其中&#xff1a; ( g(n) ) 是从起点到当前节点的实际代价。( h(n) ) 是从当前节点到目标节点的启发式…...

MyBatis 如何创建 SqlSession 对象的?

MyBatis 创建 SqlSession 对象的过程主要由 SqlSessionFactory 接口及其实现类来完成。以下是详细步骤&#xff1a; 1. SqlSessionFactory 接口: SqlSessionFactory 是 MyBatis 的核心接口之一&#xff0c;它负责创建 SqlSession 对象。 你可以将 SqlSessionFactory 视为 Sql…...

微服务》》四个问题

客户端如何访问 API 网关 如 Core中 Ocelot技术 服务如何治理 服务注册与发现 如 Core中 的 consul技术 服务挂了怎么办 可以利用 重试机制、限流、熔断、降级等 服务之间通信问题 》》同步 1. Http 对外 跨防火墙 【 序列化、反序列化 2 &#xff08; 因为http是应用层…...

CockroachDB MCP -cursor适用

CockroachDB MCP 服务器 GitHub仓库置顶 这是一个用于 Cursor 的 CockroachDB MCP 服务器&#xff0c;基于 Model Context Protocol (MCP) 规范实现&#xff0c;可以让你在 Cursor 中直接与 CockroachDB 数据库交互。 功能 连接到 CockroachDB 数据库获取数据库中的所有表获…...

GOC学习

for(int i1;i<5;i){//这里的所有语句都会被执行 5 次 } int main(){pen.a(200,16,1,0).a(200,-16,1,0);pen.rt(16).fd(200).bk(200);pen.lt(32).fd(200).bk(200);///pen.rt(-32).fd(200).bk(200);for(int i1;i<5;i){pen.a(200,16,1,0).a(200,-16,1,0);pen.rt(16).fd(200)…...

【机器学习】基于t-SNE的MNIST数据集可视化探索

一、前言 在机器学习和数据科学领域&#xff0c;高维数据的可视化是一个极具挑战但又至关重要的问题。高维数据难以直观地理解和分析&#xff0c;而有效的可视化方法能够帮助我们发现数据中的潜在结构、模式和关系。本文以经典的MNIST手写数字数据集为例&#xff0c;探讨如何利…...

Vscode工具开发Vue+ts项目时vue文件ts语法报错-红波浪线等

Vscode工具开发Vuets项目时vue文件ts语法报错-红波浪线等 解决方案 问题如题描述&#xff0c;主要原因是开发工具使用的代码检查与项目的中的ts不一致导导致&#xff0c;解决办法&#xff0c;修改 vscode 中&#xff0c; 快捷键&#xff1a;command shift p, 输入&#xff…...

Python在数据处理中的应用:从入门到精通

活动发起人小虚竹 想对你说&#xff1a; 这是一个以写作博客为目的的创作活动&#xff0c;旨在鼓励大学生博主们挖掘自己的创作潜能&#xff0c;展现自己的写作才华。如果你是一位热爱写作的、想要展现自己创作才华的小伙伴&#xff0c;那么&#xff0c;快来参加吧&#xff01…...

vue3实现跨页面缓存

避免频繁向后端发送请求,vue3中,可以用缓存机制,为了实现跨页面缓存,可以把缓存放到localsotrage里面 关键代码: const globalCache JSON.parse(localStorage.getItem(globalCache)) || {}; 然后加一个forceRefresh关键字, const fetchData async (forceRefresh false) …...

YOLO优化之多信息融合MIF

设计背景 在目标检测领域,随着深度学习技术的不断进步,研究者们一直在寻求提高模型性能和效率的方法。其中, 多模态数据融合 作为一种有效的策略,近年来受到了广泛关注。多模态融合旨在将来自不同传感器或模态的数据进行整合,以提供更全面、丰富的信息供模型学习和推断。…...

人工智能与人的智能,改变一生的思维模型【8】逆向思维

逆向偏差思维模型&#xff1a;顶尖高手如何「反常识」破局 &#xff08;斯坦福决策科学中心认证的逆向思考框架&#xff09; 一、直击本质&#xff1a;什么是逆向偏差思维&#xff1f; 定义&#xff1a; 逆向偏差思维是一种主动对抗本能认知倾向的决策模式&#xff0c;通过系…...

Python 科学计算与机器学习入门:NumPy + Scikit-Learn 实战指南

Langchain系列文章目录 01-玩转LangChain&#xff1a;从模型调用到Prompt模板与输出解析的完整指南 02-玩转 LangChain Memory 模块&#xff1a;四种记忆类型详解及应用场景全覆盖 03-全面掌握 LangChain&#xff1a;从核心链条构建到动态任务分配的实战指南 04-玩转 LangChai…...

深入理解 Qt 系统托盘图标:创建自定义的系统托盘图标类

文章目录 深入理解 Qt 系统托盘图标&#xff1a;创建自定义的系统托盘图标类1. 什么是 QSystemTrayIcon&#xff1f;2. 自定义系统托盘图标类&#xff1a;SysTraylcon3. 代码解析1. **类的定义**2. **构造函数&#xff1a;SysTraylcon::SysTraylcon(QWidget *parent)**3. **ini…...

DeepSeek-R1 面试 -—— GRPO

DeepSeek训练中应用的GRPO算法&#xff0c;它源自于强化学习领域的PPO算法。GRPO与PPO算法之间存在哪些差异&#xff1f;这两种算法各自的优劣何在&#xff1f;为何DeepSeek选择采用GRPO算法而非PPO算法&#xff1f;本文将对这些问题提供解答。 一、PPO算法 PPO&#xff08;Pr…...

AI作曲DiffRhythm原理及本地部署

1.原理简介 最近AI在音乐生成方面的进展引起了极大的关注&#xff0c;但现有的方法面临着严重的限制。一些当前的生成模型只能合成人声或伴奏轨道。虽然一些模型可以生成组合的人声和伴奏&#xff0c;但它们通常依赖于精心设计的多阶段级联架构和复杂的数据管道&#xff0c;阻…...

农业电商|基于SprinBoot+vue的农业电商服务系统(源码+数据库+文档)

农业电商服务系统 目录 基于SprinBootvue的农业电商服务系统 一、前言 二、系统设计 三、系统功能设计 5.1系统功能实现 5.2后台模块实现 5.2.1管理员模块实现 5.2.2商家模块实现 四、数据库设计 五、核心代码 六、论文参考 七、最新计算机毕设选题推荐 八、源码…...

深度学习有哪些算法?

深度学习包含多种算法和模型&#xff0c;广泛应用于图像处理、自然语言处理、语音识别等领域。以下是主要分类及代表性算法&#xff1a; 一、基础神经网络 多层感知机&#xff08;MLP&#xff09; 最简单的深度学习模型&#xff0c;由多个全连接层组成&#xff0c;用于分类和回…...

鸿蒙开发-一多开发之媒体查询功能

在HarmonyOS中&#xff0c;使用ArkTS语法实现响应式布局的媒体查询是一个强大的功能&#xff0c;它允许开发者根据不同的设备特征&#xff08;如屏幕尺寸、屏幕方向等&#xff09;动态地调整UI布局和样式。以下是一个使用媒体查询实现响应式布局的实例&#xff1a; 1. 导入必要…...

历年华中科技大学计算机考研复试上机真题

历年华中科技大学计算机考研复试上机真题 2022华中科技大学计算机考研复试上机真题 2021华中科技大学计算机考研复试上机真题 2019华中科技大学计算机考研复试上机真题 在线评测&#xff1a;https://pgcode.cn 八进制 题目描述 输入一个整数&#xff0c;将其转换成八进制数…...

卷积神经网络(CNN)的主要架构

卷积神经网络&#xff08;CNN, Convolutional Neural Networks&#xff09;是深度学习中最重要的模型之一&#xff0c;广泛应用于计算机视觉、目标检测、语义分割等任务。自 LeNet 诞生以来&#xff0c;CNN 结构经历了多个重要发展阶段&#xff0c;出现了许多经典架构&#xff…...

IDEA:项目结构不见了,项目文件消失解决

IDEA&#xff1a;看不见目录结构了。 1、确认项目是否仍存在&#xff1a;检查项目文件夹是否仍然存在于磁盘上。如果项目文件夹被删除或移动了&#xff0c;您需要将其还原或重新导入到IDEA中。 2、重新导入项目&#xff1a;如果项目文件存在&#xff0c;在 IDEA 中找到项目文…...

基于ssm的宠物医院信息管理系统(全套)

一、系统架构 前端&#xff1a;html | layui | vue | element-ui 后端&#xff1a;spring | springmvc | mybatis 环境&#xff1a;jdk1.8 | mysql | maven | tomcat | idea | nodejs 二、代码及数据库 三、功能介绍 01. web端-首页1 02. web端-首页…...

How to install a package in offline scenario in Ubuntu 24.04

概述 做过信创项目的兄弟们在工作上每天可能面对很多需要解决的问题&#xff0c;不过&#xff0c;有一类问题可能是大家经常遇的&#xff0c;比方说&#xff0c;有时候我们不得不硬着头皮在离线生产环境中安装某些软件包&#xff0c;相信很多兄弟被这种细碎的小事搞得焦头烂额…...

将pdf或者word转换成base64格式

废话不多说直接上代码&#xff1a; function fileToBase64(file) {return new Promise((resolve, reject) > {const reader new FileReader();reader.readAsDataURL(file);reader.onload function (event) {const base64Data event.target.result.split(,)[1];resolve(b…...

使用Nodejs基于DeepSeek加chromadb实现RAG检索增强生成 本地知识库

定义 检索增强生成&#xff08;RAG&#xff09;的基本定义 检索增强生成&#xff08;Retrieval-Augmented Generation&#xff0c;简称RAG&#xff09;是一种结合了信息检索技术与语言生成模型的人工智能技术。RAG通过从外部知识库中检索相关信息&#xff0c;并将其作为提示&…...

乐观锁VS分布式锁实现抢单服务

司机开始接单&#xff0c;乘客填写出发地——目的地&#xff0c;开始下单 service-order模块 Operation(summary"司机抢单") GetMapping("/robNewOrder/{driverId}/{orderId}") public Result<Boolean> robNewOrder(PathVariable Long driverId,P…...

通过特征值和特征向量实现的图像压缩和特征提取

前文&#xff0c;我们在学习人工智能的线性代数基础的时候&#xff0c;就了解到&#xff0c;矩阵在人工智能中被广泛使用&#xff0c;接下来我们就从大家非常常见的图像开始&#xff0c;深度理解矩阵在人工智能中的应用。有关线性代数基础的文章可以看的我CSDN:人工智能中的线性…...

ranger集成starrock报错

org.apache.ranger.plugin.client.HadoopException: initConnection: Unable to connect to StarRocks instance, please provide valid value of field : {jdbc.driverClassName}.. com.mysql.cj.jdbc.Driver. 可能的原因 JDBC 驱动缺失&#xff1a;运行环境中没有安装 MySQL …...

第J2周:ResNet50V2算法实现01(Tensorflow硬编码版)

&#x1f368; 本文为&#x1f517;365天深度学习训练营 中的学习记录博客&#x1f356; 原作者&#xff1a;K同学啊 目标 使用tensorflow实现ResNetV50V2的网络结构。本次根据第一层的细节手动硬编码&#xff0c;没有任何的优化&#xff0c;只为了更好的理解细节。 目录结构&…...

论文分享 | HE-Nav: 一种适用于复杂环境中空地机器人的高性能高效导航系统

阿木实验室始终致力于通过开源项目和智能无人机产品&#xff0c;为全球无人机开发者提供强有力的技术支持&#xff0c;并推出了开源项目校园赞助活动&#xff0c;助力高校学子在学术研究与技术创新中取得更大突破。近日&#xff0c;香港大学王俊铭同学&#xff0c;基于阿木实验…...

【mysql】centOS7安装mysql详细操作步骤!—通过tar包方式

【mysql】centOS7安装mysql详细操作步骤&#xff01; linux系统安装mysql版本 需要 root 权限&#xff0c;使用 root 用户进行命令操作。使用tar文件包&#xff0c;安装&#xff0c;gz包也可以但是还需要配置用户&#xff0c;tar包虽然大&#xff0c;但是全啊&#xff01; 1. …...

java学习笔记1

程序编译步骤 java程序执行步骤 相关代码及解释&#xff1a; /* 对第一个java程序进行总结 1. java程序编写-编译-运行的过程 编写&#xff1a;我们将编写的java代码保存在以".java"结尾的源文件中 编译&#xff1a;使用javac.exe命令编译我们的java源文件。格式&am…...

强大的数据库DevOps工具:NineData 社区版

本文作者司马辽太杰&#xff0c; gzh&#xff1a;程序猿读历史 在业务快速变化与数据安全日益重要的今天&#xff0c;生产数据库变更管理、版本控制、数据使用是数据库领域的核心挑战之一。传统的解决方式往往采用邮件或即时通讯工具发起审批流程&#xff0c;再通过堡垒机直连数…...

「Unity3D」UGUI运行时设置元素的锚点Anchor,维持元素Rect的显示不变,即待在原处

在编辑器中&#xff0c;通过设置Raw edit mode&#xff0c;可以切换两种&#xff0c;元素锚点的改变模式&#xff1a; 一种是锚点单独改变&#xff0c;即&#xff1a;不开启原始模式&#xff0c;保持原样&#xff0c;改变anchoredPosition与sizeDelta。一种是锚点联动显示&…...

深入解析大语言模型的 Function Call 实现—— 以 Qwen2.5为例

引言 在现代大语言模型&#xff08;LLM&#xff09;中&#xff0c;Function Call&#xff08;函数调用&#xff09;能力极大地提升了模型的实用性&#xff0c;使其能够调用外部 API、执行复杂计算或获取实时数据。例如&#xff0c;在 OpenAI API 和 Qwen2.5-7B-Instruct 这样的…...

鸿蒙路由 HMrouter 配置及使用一

1、学习链接 HMRouter地址 https://gitee.com/hadss/hmrouter/blob/dev/HMRouterLibrary/README.md 2、工程配置 下载安装 ohpm install hadss/hmrouter 添加编译插件配置 在工程目录下的build-profile.json5中&#xff0c;配置useNormalizedOHMUrl属性为true (我这项目创…...

驾驭 DeepSeek 科技之翼,翱翔现代学习新天际

在当今这个信息爆炸的时代&#xff0c;学习的方式和途径正在经历着前所未有的变革。人工智能技术的飞速发展&#xff0c;为我们的学习带来了全新的机遇和挑战。DeepSeek 作为一款强大的大语言模型&#xff0c;凭借其卓越的性能和丰富的功能&#xff0c;为现代学习注入了新的活力…...