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

分治思想 排序数组

题目

这是一道经典的关于分治思想的算法题,适合刚接触分治的小白。

. - 力扣(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];}
};

相关文章:

分治思想 排序数组

题目 这是一道经典的关于分治思想的算法题&#xff0c;适合刚接触分治的小白。 . - 力扣&#xff08;LeetCode&#xff09; 思路 采用递归分治的思想&#xff0c;也就是快速排序的模拟&#xff0c;这里先确定每趟递归的作用&#xff1a; 在一个规定的区间内&#xff0c;随机…...

通用前端分页插件

/*** >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>* 分页组件* >>>>>>>>>>>>>>>>>>>…...

jEasyUI 扩展编辑器

jEasyUI 扩展编辑器 jEasyUI 是一个基于 jQuery 的前端框架,它提供了一系列的组件,用于快速构建交互式的网页界面。这些组件包括布局、窗口、数据网格等,但有时候,开发者可能需要更多的定制化功能,这时候就需要使用 jEasyUI 的扩展编辑器。 什么是 jEasyUI 扩展编辑器 …...

腾讯课堂停服,付费课程怎么观看!!!

腾讯课堂十月1停服拉&#xff0c;大家的付费课程赶紧保存收获一波啊&#xff0c; 爬虫工程师手拿把掐啦&#xff01;&#xff01;&#xff01;...

C# 桥接模式

栏目总目录 概念 桥接模式&#xff08;Bridge Pattern&#xff09;是一种结构型设计模式&#xff0c;用于将抽象部分与具体实现部分分离&#xff0c;使它们可以独立地变化。这种设计模式通过创建一个连接&#xff08;桥&#xff09;来将抽象和实现部分分离&#xff0c;从而允许…...

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 首先&#xff0c;使用pip安装Pytest&#xff1a; pip install pytest单元测试 单元测试用于测试单个模块或函数的功能。假设我们有一个简单的Python模块…...

Java面试必看!知己知彼才能百战百胜,如何做好面试前的准备?

随着 Java 这个赛道的不断内卷&#xff0c;这两年&#xff0c;Java 程序员的面试&#xff0c;从原来的常规八股文&#xff08;有 标准答案&#xff09;到现在&#xff0c;以项目、场景问题、技术深度思考为主&#xff0c;逐步转变成没有标准答案&#xff0c; 需要大家基于自己的…...

[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&#xff08;管道&#xff09;是huggingface transformers库中一种极简方式使用大模型推理的抽象&#xff0c;将所有大模型分为音频&#xff08;Audio&#xff09;、计算机视觉&#xff08;Computer vision&#xff09;、自然语言处理&#x…...

前端入门知识分享:HTML 页面中 head 标签之间的代码详解

前端入门知识分享&#xff1a;HTML 页面中 head 标签之间的代码详解 在HTML代码中HEAD之间的代码就是网页头元素&#xff0c;里面的内容不会显现在网页中&#xff0c;因此很容易被别人遗忘&#xff0c;但它对网页的渲染和功能性至关重要。如果能够掌握它的概念和使用方法&#…...

【Spring Boot】手撕搜索引擎项目,深度复盘在开发中的重难点和总结(长达两万6千字的干货,系好安全带,要发车了......)

目录 搜索引擎搜索引擎的核心思路 一、解析模块1.1 枚举所有文件1.2 解析每个文件的标题&#xff0c;URL以及正文1.2.1 解析标题1.2.2 解析URL1.2.3 解析正文 1.3 线程池优化代码 二 、创建排序模块2.1 构建正排索引2.2 构建倒排索引2.3 序列化2.4 反序列化 三、搜索模块3.1 引…...

测试面试宝典(四十二)—— 接口测试什么时候介入

回答一&#xff1a; 接口测试通常在项目开发的早期阶段就可以介入。一般来说&#xff0c;在接口定义和设计完成后&#xff0c;开发人员开始进行接口的初步实现时&#xff0c;测试人员就可以着手进行接口测试了。比如&#xff0c;在需求分析和评审阶段&#xff0c;明确了接口的功…...

【Elasticsearch】Elasticsearch的分片和副本机制

文章目录 &#x1f4d1;前言一、分片&#xff08;Shard&#xff09;1.1 分片的定义1.2 分片的重要性1.3 分片的类型1.4 分片的分配 二、副本&#xff08;Replica&#xff09;2.1 副本的定义2.2 副本的重要性2.3 副本的分配 三、分片和副本的机制3.1 分片的创建和分配3.2 数据写…...

鸿蒙开发入门指南

(创作不易&#xff0c;感谢有你&#xff0c;你的支持&#xff0c;就是我前行的最大动力&#xff0c;如果看完对你有帮助&#xff0c;请留下您的足迹&#xff09; 目录 引言 一、鸿蒙系统概述 1.1 简介 1.2 鸿蒙开发的优势 二、鸿蒙开发环境搭建 2.1 安装鸿蒙DevEco Studi…...

从分散到整合,细说比特币发展史

原文标题&#xff1a;《Layered Bitcoin》 撰文&#xff1a;Saurabh Deshpande 编译&#xff1a;Chris&#xff0c;Techub News 古往今来&#xff0c;货币在社会中都具有三个关键的功能&#xff1a;财富的储存手段、交换媒介和计量单位。虽然货币的形式在不断变化&#xff0c…...

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日&#xff0c;2024向星力未来数据技术峰会期间&#xff0c;在峰会现场来宾共同见证下&#xff0c;星环科技与宁夏银行“大数据联合实验室”正式揭牌&#xff0c;宁夏银行股份有限公司首席信息官崔彦刚与星环科技副总裁邱磊共同为联合实验室揭牌。 星环科技与宁夏银行借…...

React native页面突然白屏

背景&#xff1a;某个时间段突然收到破100的用户反馈&#xff0c;商品详情&#xff08;React native页面&#xff09;打不开&#xff0c;一片空白&#xff0c;无法正常使用 设备&#xff1a;部分华为手机Harmoney4.0&#xff0c;华为相关Android系统 可临时恢复方案&#xff…...

微信支付回调通知收不到的5个隐藏坑(附.NET Core实战解决方案)

微信支付回调通知失效的深度排查与.NET Core实战指南 当支付流程顺利完成但回调通知却神秘消失时&#xff0c;这种"薛定谔式的支付成功"往往让开发者陷入调试泥潭。本文将揭示五个容易被忽视的技术暗礁&#xff0c;并提供可直接集成到生产环境的.NET Core解决方案。 …...

别再ping IP了!手把手教你给ZeroTier虚拟网络里的设备起个‘好记’的名字(DNS/mDNS实战)

告别IP记忆困扰&#xff1a;ZeroTier网络中的智能命名方案实战指南 每次在ZeroTier虚拟网络中访问设备时&#xff0c;你是否也厌倦了反复查看和输入那串冗长的IP地址&#xff1f;想象一下&#xff0c;当你想连接家庭NAS时&#xff0c;只需输入nas.home就能立即访问&#xff0c…...

2026最权威一键生成论文工具榜单:这些被高校和导师悄悄推荐的软件你用了吗

一键生成论文工具正成为学术研究的重要助力&#xff0c;其高效性与专业性在近年来得到广泛认可。依托权威检测平台数据、高校实测反馈及用户真实评价&#xff0c;这些工具已逐步成为科研工作者和学生群体的得力助手。本文将盘点2026年最受高校和导师推荐的一键生成论文软件&…...

OpenClaw调试技巧:Qwen3-32B任务失败排查手册

OpenClaw调试技巧&#xff1a;Qwen3-32B任务失败排查手册 1. 为什么需要这份手册&#xff1f; 上周我尝试用OpenClaw自动整理项目文档时&#xff0c;遇到了一个诡异现象&#xff1a;同样的任务在白天能顺利完成&#xff0c;深夜运行时却频繁报错。经过72小时的问题追踪&#…...

高通平台USB充电背后的秘密:从SBL1阶段到Kernel的电池ID识别全解析

高通平台USB充电与电池ID识别的深度技术解析 在Android设备开发中&#xff0c;电源管理系统的稳定性直接影响用户体验。作为底层驱动工程师&#xff0c;理解高通平台从硬件到软件的完整充电流程至关重要。本文将深入剖析从XBL阶段到Kernel层的电池识别机制&#xff0c;揭示BATT…...

Step3-VL-10B部署案例:金融APP界面自动化测试,覆盖85%人工回归用例

Step3-VL-10B部署案例&#xff1a;金融APP界面自动化测试&#xff0c;覆盖85%人工回归用例 1. 项目背景与痛点 金融APP的每一次版本更新&#xff0c;都伴随着一场紧张的回归测试。测试团队需要反复验证登录、转账、理财购买、账单查询等几十个核心功能&#xff0c;确保新代码…...

OpenClaw知识库集成:Qwen3-VL:30B连接飞书文档中心

OpenClaw知识库集成&#xff1a;Qwen3-VL:30B连接飞书文档中心 1. 为什么需要智能文档助手 上个月整理季度技术文档时&#xff0c;我对着飞书里上百个分散的文档链接发愁——每次找资料都要在搜索框反复尝试关键词&#xff0c;遇到表格和图表更要逐页核对。直到发现OpenClaw能…...

ESP32上给LVGL做个‘懒加载’:分页与动态读取大文本的实战对比(附代码)

ESP32上LVGL大文本显示优化&#xff1a;分页加载与动态读取的深度对比与实践 在嵌入式设备上处理大文本显示一直是开发者面临的挑战之一。当我们在ESP32这样的资源受限平台上使用LVGL&#xff08;Light and Versatile Graphics Library&#xff09;显示超长文本时&#xff0c;如…...

OpenClaw+ollama-QwQ-32B实战:自动化处理100份简历筛选

OpenClawollama-QwQ-32B实战&#xff1a;自动化处理100份简历筛选 1. 为什么选择自动化简历筛选 去年团队扩张时&#xff0c;我作为技术负责人参与了简历初筛工作。面对雪片般飞来的PDF简历&#xff0c;连续三天熬夜到凌晨两点手动整理关键信息后&#xff0c;我意识到必须寻找…...

如何安全提取Chrome浏览器密码:3种实用方法完全指南

如何安全提取Chrome浏览器密码&#xff1a;3种实用方法完全指南 【免费下载链接】chromepass Get all passwords stored by Chrome on WINDOWS. 项目地址: https://gitcode.com/gh_mirrors/chr/chromepass 在数字生活中&#xff0c;你是否遇到过忘记网站密码的困扰&…...