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

PHP和Node.js哪个更爽?

先说结论&#xff0c;rust完胜。 php&#xff1a;laravel&#xff0c;swoole&#xff0c;webman&#xff0c;最开始在苏宁的时候写了几年php&#xff0c;当时觉得php真的是世界上最好的语言&#xff0c;因为当初活在舒适圈里&#xff0c;不愿意跳出来&#xff0c;就好比当初活在…...

安宝特方案丨XRSOP人员作业标准化管理平台:AR智慧点检验收套件

在选煤厂、化工厂、钢铁厂等过程生产型企业&#xff0c;其生产设备的运行效率和非计划停机对工业制造效益有较大影响。 随着企业自动化和智能化建设的推进&#xff0c;需提前预防假检、错检、漏检&#xff0c;推动智慧生产运维系统数据的流动和现场赋能应用。同时&#xff0c;…...

SCAU期末笔记 - 数据分析与数据挖掘题库解析

这门怎么题库答案不全啊日 来简单学一下子来 一、选择题&#xff08;可多选&#xff09; 将原始数据进行集成、变换、维度规约、数值规约是在以下哪个步骤的任务?(C) A. 频繁模式挖掘 B.分类和预测 C.数据预处理 D.数据流挖掘 A. 频繁模式挖掘&#xff1a;专注于发现数据中…...

OkHttp 中实现断点续传 demo

在 OkHttp 中实现断点续传主要通过以下步骤完成&#xff0c;核心是利用 HTTP 协议的 Range 请求头指定下载范围&#xff1a; 实现原理 Range 请求头&#xff1a;向服务器请求文件的特定字节范围&#xff08;如 Range: bytes1024-&#xff09; 本地文件记录&#xff1a;保存已…...

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

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

论文浅尝 | 基于判别指令微调生成式大语言模型的知识图谱补全方法(ISWC2024)

笔记整理&#xff1a;刘治强&#xff0c;浙江大学硕士生&#xff0c;研究方向为知识图谱表示学习&#xff0c;大语言模型 论文链接&#xff1a;http://arxiv.org/abs/2407.16127 发表会议&#xff1a;ISWC 2024 1. 动机 传统的知识图谱补全&#xff08;KGC&#xff09;模型通过…...

Python如何给视频添加音频和字幕

在Python中&#xff0c;给视频添加音频和字幕可以使用电影文件处理库MoviePy和字幕处理库Subtitles。下面将详细介绍如何使用这些库来实现视频的音频和字幕添加&#xff0c;包括必要的代码示例和详细解释。 环境准备 在开始之前&#xff0c;需要安装以下Python库&#xff1a;…...

零基础设计模式——行为型模式 - 责任链模式

第四部分&#xff1a;行为型模式 - 责任链模式 (Chain of Responsibility Pattern) 欢迎来到行为型模式的学习&#xff01;行为型模式关注对象之间的职责分配、算法封装和对象间的交互。我们将学习的第一个行为型模式是责任链模式。 核心思想&#xff1a;使多个对象都有机会处…...

成都鼎讯硬核科技!雷达目标与干扰模拟器,以卓越性能制胜电磁频谱战

在现代战争中&#xff0c;电磁频谱已成为继陆、海、空、天之后的 “第五维战场”&#xff0c;雷达作为电磁频谱领域的关键装备&#xff0c;其干扰与抗干扰能力的较量&#xff0c;直接影响着战争的胜负走向。由成都鼎讯科技匠心打造的雷达目标与干扰模拟器&#xff0c;凭借数字射…...

C++八股 —— 单例模式

文章目录 1. 基本概念2. 设计要点3. 实现方式4. 详解懒汉模式 1. 基本概念 线程安全&#xff08;Thread Safety&#xff09; 线程安全是指在多线程环境下&#xff0c;某个函数、类或代码片段能够被多个线程同时调用时&#xff0c;仍能保证数据的一致性和逻辑的正确性&#xf…...