分治思想 排序数组
题目
这是一道经典的关于分治思想的算法题,适合刚接触分治的小白。
. - 力扣(LeetCode)

思路
采用递归分治的思想,也就是快速排序的模拟,这里先确定每趟递归的作用:
在一个规定的区间内,随机选择一个key,将key放在正确的位置,也就是左边的元素都比它小,右边的元素都比它大,实现方法如下:
通过三个指针(i,left,right)将数组划分为4个区域。

我们确保处理过程中:
left左边全是<key的元素
left+1到i-1全是==key的元素
i到right-1都是待扫描的元素
right右边都是>key的元素
当i和right相遇时循环结束
最后数组就被划分为3个区域:
left左边全是<key的元素,left+1到right-1全是==key的元素,right右边都是>key的元素。
最后再递归处理左边<key的区间和右边>key的区间,进行上述相同的操作。
AC代码:
class Solution {
public:vector<int> sortArray(vector<int>& nums) {srand(time(NULL));qsort(nums,0,nums.size() - 1);return nums;}void qsort(vector<int>& nums,int l,int r){//递归结束条件if(l>=r) return;//随机选取keyint key = GetRandM(nums,l,r);int i = l,left = l - 1,right = r + 1;//确保过程中被划分为预先设好的4个有规律的区域while(i<right){if(nums[i] < key) swap(nums[++left],nums[i++]);else if(nums[i] == key) i++;else swap(nums[--right],nums[i]);}//[l,left][left+1,right-1][right,r]//递归左右区间qsort(nums,l,left);qsort(nums,right,r);}//得到区间内一个随机元素int GetRandM(vector<int>& nums,int left,int right){int r = rand();return nums[r % (right - left + 1) + left];}
};
相关文章:
分治思想 排序数组
题目 这是一道经典的关于分治思想的算法题,适合刚接触分治的小白。 . - 力扣(LeetCode) 思路 采用递归分治的思想,也就是快速排序的模拟,这里先确定每趟递归的作用: 在一个规定的区间内,随机…...
通用前端分页插件
/*** >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>* 分页组件* >>>>>>>>>>>>>>>>>>>…...
jEasyUI 扩展编辑器
jEasyUI 扩展编辑器 jEasyUI 是一个基于 jQuery 的前端框架,它提供了一系列的组件,用于快速构建交互式的网页界面。这些组件包括布局、窗口、数据网格等,但有时候,开发者可能需要更多的定制化功能,这时候就需要使用 jEasyUI 的扩展编辑器。 什么是 jEasyUI 扩展编辑器 …...
腾讯课堂停服,付费课程怎么观看!!!
腾讯课堂十月1停服拉,大家的付费课程赶紧保存收获一波啊, 爬虫工程师手拿把掐啦!!!...
C# 桥接模式
栏目总目录 概念 桥接模式(Bridge Pattern)是一种结构型设计模式,用于将抽象部分与具体实现部分分离,使它们可以独立地变化。这种设计模式通过创建一个连接(桥)来将抽象和实现部分分离,从而允许…...
GPT-4o mini一手测评:懂得不多,但答得极快
在性能方面,GPT-4o mini 在 MMLU 上的得分为 82%,在 LMSYS 排行榜的聊天方面分数优于 GPT-4。 OpenAI 突然上线新模型 GPT-4o mini, 声称要全面取代 GPT-3.5 Turbo。 在性能方面,GPT-4o mini 在 MMLU 上的得分为 82%,在 LMSYS 排行榜的聊天方面分数优于 GPT-4。 在价格…...
Python面试题:结合Python技术,如何使用Pytest进行单元测试和集成测试
使用Pytest进行单元测试和集成测试是非常常见和有效的方法。下面是如何使用Pytest进行这些测试的详细指南。 安装Pytest 首先,使用pip安装Pytest: pip install pytest单元测试 单元测试用于测试单个模块或函数的功能。假设我们有一个简单的Python模块…...
Java面试必看!知己知彼才能百战百胜,如何做好面试前的准备?
随着 Java 这个赛道的不断内卷,这两年,Java 程序员的面试,从原来的常规八股文(有 标准答案)到现在,以项目、场景问题、技术深度思考为主,逐步转变成没有标准答案, 需要大家基于自己的…...
[Vue warn]: data functions should return an object:
仔细检查你的代码肯定有一个data()内忘记方return{}了...
.net 7和core版 SignalR
.net 7和core版 SignalR代码示例(手把手一起认识Websocket、SignalR) # 白话讲解 刚听到Websocket、SignalR有没有很迷茫,一脸懵逼的那种有没有,都是通信,这俩有什么区别,都是怎么实现的,什么时候该用哪一个, 苦于Websocket、SignalR久已,今天必须整出个一二三来,…...
【人工智能】Transformers之Pipeline(三):文本转音频(text-to-audio/text-to-speech)
一、引言 pipeline(管道)是huggingface transformers库中一种极简方式使用大模型推理的抽象,将所有大模型分为音频(Audio)、计算机视觉(Computer vision)、自然语言处理&#x…...
前端入门知识分享:HTML 页面中 head 标签之间的代码详解
前端入门知识分享:HTML 页面中 head 标签之间的代码详解 在HTML代码中HEAD之间的代码就是网页头元素,里面的内容不会显现在网页中,因此很容易被别人遗忘,但它对网页的渲染和功能性至关重要。如果能够掌握它的概念和使用方法&#…...
【Spring Boot】手撕搜索引擎项目,深度复盘在开发中的重难点和总结(长达两万6千字的干货,系好安全带,要发车了......)
目录 搜索引擎搜索引擎的核心思路 一、解析模块1.1 枚举所有文件1.2 解析每个文件的标题,URL以及正文1.2.1 解析标题1.2.2 解析URL1.2.3 解析正文 1.3 线程池优化代码 二 、创建排序模块2.1 构建正排索引2.2 构建倒排索引2.3 序列化2.4 反序列化 三、搜索模块3.1 引…...
测试面试宝典(四十二)—— 接口测试什么时候介入
回答一: 接口测试通常在项目开发的早期阶段就可以介入。一般来说,在接口定义和设计完成后,开发人员开始进行接口的初步实现时,测试人员就可以着手进行接口测试了。比如,在需求分析和评审阶段,明确了接口的功…...
【Elasticsearch】Elasticsearch的分片和副本机制
文章目录 📑前言一、分片(Shard)1.1 分片的定义1.2 分片的重要性1.3 分片的类型1.4 分片的分配 二、副本(Replica)2.1 副本的定义2.2 副本的重要性2.3 副本的分配 三、分片和副本的机制3.1 分片的创建和分配3.2 数据写…...
鸿蒙开发入门指南
(创作不易,感谢有你,你的支持,就是我前行的最大动力,如果看完对你有帮助,请留下您的足迹) 目录 引言 一、鸿蒙系统概述 1.1 简介 1.2 鸿蒙开发的优势 二、鸿蒙开发环境搭建 2.1 安装鸿蒙DevEco Studi…...
从分散到整合,细说比特币发展史
原文标题:《Layered Bitcoin》 撰文:Saurabh Deshpande 编译:Chris,Techub News 古往今来,货币在社会中都具有三个关键的功能:财富的储存手段、交换媒介和计量单位。虽然货币的形式在不断变化,…...
TreeSelect增加可筛选功能
TreeSelect官方可筛选示例 <template><el-tree-selectv-model"value":data"data"filterablestyle"width: 240px"/><el-divider /><el-divider />filter node method:<el-tree-selectv-model"value":data&q…...
星环科技与宁夏银行“大数据联合实验室”揭牌,持续打造金融科技新范式
5月30-31日,2024向星力未来数据技术峰会期间,在峰会现场来宾共同见证下,星环科技与宁夏银行“大数据联合实验室”正式揭牌,宁夏银行股份有限公司首席信息官崔彦刚与星环科技副总裁邱磊共同为联合实验室揭牌。 星环科技与宁夏银行借…...
React native页面突然白屏
背景:某个时间段突然收到破100的用户反馈,商品详情(React native页面)打不开,一片空白,无法正常使用 设备:部分华为手机Harmoney4.0,华为相关Android系统 可临时恢复方案ÿ…...
深入解析NAND Flash基础操作与系统集成——从阵列结构到多Die协同
1. NAND Flash基础结构与工作原理 NAND Flash存储器是现代存储系统的核心组件,从U盘到企业级SSD都依赖这项技术。要理解它的强大之处,得先从它的物理结构说起——想象一个巨大的立体停车场,每个停车位就是一个存储单元,而控制电路…...
提升嵌入式代码注释质量的工具与技术方案
提升代码注释质量的实用工具与技术方案1. 代码注释工具概述1.1 代码注释的重要性在嵌入式系统开发中,良好的代码注释是保证项目可维护性的关键因素。专业的注释工具能够帮助开发者:创建可视化注释,提升代码可读性生成标准化的文档结构维护代码…...
三步掌握Dark Reader:从入门到精通的护眼浏览解决方案
三步掌握Dark Reader:从入门到精通的护眼浏览解决方案 【免费下载链接】darkreader Dark Reader Chrome and Firefox extension 项目地址: https://gitcode.com/gh_mirrors/da/darkreader Dark Reader是一款能够为任何网站启用深色模式的浏览器扩展ÿ…...
别再让PowerBI报告挤成一团了!用按钮+书签,一个页面搞定趋势和明细分析
PowerBI交互设计进阶:用按钮与书签打造空间魔术 当业务分析报告遇上数据爆炸时代,信息过载与界面拥挤成为每个分析师挥之不去的噩梦。我曾见过某零售企业的季度分析仪表板——12个图表密密麻麻挤在A4纸大小的画布上,趋势线相互缠绕ÿ…...
别再让AI失忆了!手把手教你用Mem0为ChatGPT添加长期记忆(附Next.js实战代码)
为Next.js聊天应用注入长期记忆:Mem0集成实战指南 当你的AI助手开始记住用户的咖啡偏好和生日祝福时,整个交互体验会发生质的变化。本文将带你从零开始,在Next.js应用中实现这种"记忆魔法"。 1. 环境准备与Mem0初始化 首先创建一个…...
从Python转C++必看:C++20的starts_with/ends_with和Python有何不同?5个易错点详解
从Python转C必看:C20的starts_with/ends_with和Python有何不同?5个易错点详解 当你在Python中熟练使用startswith()和endswith()多年后,突然切换到C20的starts_with和ends_with,可能会觉得"这不就是换个语法吗?&q…...
NaViL-9B开源模型实战:媒体内容审核平台图文敏感信息识别案例
NaViL-9B开源模型实战:媒体内容审核平台图文敏感信息识别案例 1. 模型与平台介绍 NaViL-9B是上海人工智能实验室研发的原生多模态大语言模型,能够同时处理文本和图像信息。这个开源模型特别适合构建智能内容审核系统,因为它具备以下核心能力…...
目标检测实战:从VOC XML到YOLO格式的自动化数据流水线
1. 为什么需要VOC转YOLO格式 在目标检测任务中,数据格式的统一性直接影响着模型训练的效率。VOC(PASCAL VOC)和YOLO是两种最常见的标注格式,但它们的存储方式截然不同。VOC采用XML文件记录目标的类别和边界框坐标,而YO…...
OpenClaw+Qwen3.5-4B-Claude:个人知识库自动更新系统
OpenClawQwen3.5-4B-Claude:个人知识库自动更新系统 1. 为什么需要自动化知识管理 作为一个技术从业者,我每天都会接触到大量信息——技术博客、论文摘要、行业动态、代码库更新等等。过去三年里,我尝试过各种笔记工具和知识管理方法&#…...
ANARCI抗体序列分析工具:从入门到精通的专业指南
ANARCI抗体序列分析工具:从入门到精通的专业指南 【免费下载链接】ANARCI Antibody Numbering and Antigen Receptor ClassIfication 项目地址: https://gitcode.com/gh_mirrors/an/ANARCI ANARCI(Antibody Numbering and Antigen Receptor Class…...
