分治思想 排序数组
题目
这是一道经典的关于分治思想的算法题,适合刚接触分治的小白。
. - 力扣(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系统 可临时恢复方案ÿ…...
RestClient
什么是RestClient RestClient 是 Elasticsearch 官方提供的 Java 低级 REST 客户端,它允许HTTP与Elasticsearch 集群通信,而无需处理 JSON 序列化/反序列化等底层细节。它是 Elasticsearch Java API 客户端的基础。 RestClient 主要特点 轻量级ÿ…...
conda相比python好处
Conda 作为 Python 的环境和包管理工具,相比原生 Python 生态(如 pip 虚拟环境)有许多独特优势,尤其在多项目管理、依赖处理和跨平台兼容性等方面表现更优。以下是 Conda 的核心好处: 一、一站式环境管理:…...
css实现圆环展示百分比,根据值动态展示所占比例
代码如下 <view class""><view class"circle-chart"><view v-if"!!num" class"pie-item" :style"{background: conic-gradient(var(--one-color) 0%,#E9E6F1 ${num}%),}"></view><view v-else …...
线程同步:确保多线程程序的安全与高效!
全文目录: 开篇语前序前言第一部分:线程同步的概念与问题1.1 线程同步的概念1.2 线程同步的问题1.3 线程同步的解决方案 第二部分:synchronized关键字的使用2.1 使用 synchronized修饰方法2.2 使用 synchronized修饰代码块 第三部分ÿ…...
Opencv中的addweighted函数
一.addweighted函数作用 addweighted()是OpenCV库中用于图像处理的函数,主要功能是将两个输入图像(尺寸和类型相同)按照指定的权重进行加权叠加(图像融合),并添加一个标量值&#x…...
12.找到字符串中所有字母异位词
🧠 题目解析 题目描述: 给定两个字符串 s 和 p,找出 s 中所有 p 的字母异位词的起始索引。 返回的答案以数组形式表示。 字母异位词定义: 若两个字符串包含的字符种类和出现次数完全相同,顺序无所谓,则互为…...
蓝桥杯3498 01串的熵
问题描述 对于一个长度为 23333333的 01 串, 如果其信息熵为 11625907.5798, 且 0 出现次数比 1 少, 那么这个 01 串中 0 出现了多少次? #include<iostream> #include<cmath> using namespace std;int n 23333333;int main() {//枚举 0 出现的次数//因…...
Spring Cloud Gateway 中自定义验证码接口返回 404 的排查与解决
Spring Cloud Gateway 中自定义验证码接口返回 404 的排查与解决 问题背景 在一个基于 Spring Cloud Gateway WebFlux 构建的微服务项目中,新增了一个本地验证码接口 /code,使用函数式路由(RouterFunction)和 Hutool 的 Circle…...
佰力博科技与您探讨热释电测量的几种方法
热释电的测量主要涉及热释电系数的测定,这是表征热释电材料性能的重要参数。热释电系数的测量方法主要包括静态法、动态法和积分电荷法。其中,积分电荷法最为常用,其原理是通过测量在电容器上积累的热释电电荷,从而确定热释电系数…...
在Mathematica中实现Newton-Raphson迭代的收敛时间算法(一般三次多项式)
考察一般的三次多项式,以r为参数: p[z_, r_] : z^3 (r - 1) z - r; roots[r_] : z /. Solve[p[z, r] 0, z]; 此多项式的根为: 尽管看起来这个多项式是特殊的,其实一般的三次多项式都是可以通过线性变换化为这个形式…...
