【算法】分治-快排

个人主页 : zxctscl
如有转载请先通知

题目

  • 前言
  • 1. 75. 颜色分类
    • 1.1 分析
    • 1.2 代码
  • 2. 912. 排序数组
    • 2.1 分析
    • 2.2 代码
  • 3. 215. 数组中的第K个最大元素
    • 3.1 分析
    • 3.2 代码
  • 4. LCR 159. 库存管理 III
    • 4.1 分析
    • 4.2 代码

前言

分治就是分而治之

1. 75. 颜色分类

在这里插入图片描述

1.1 分析

就是把数组中的元素分为三块,0全部在左边,1全部在中间,2全部在右边。
这里要用到三个指针,一个i指针用来遍历,一个left用来存放0区域的最后侧,一个用来存放2区域的最左侧。
那么区间就分成了4个
在这里插入图片描述
只需要判断nums[i]的值是什么,然后把它放在对应区域。把数组遍历一遍就行,最终i只要等于right就结束遍历,此时中间已经没有要确定区域的数了。
在这里插入图片描述

1.2 代码

class Solution {
public:void sortColors(vector<int>& nums) {int left=-1,right=nums.size(),i=0;while(i<right){if(nums[i]==0){swap(nums[++left],nums[i++]);}else if(nums[i]==1)i++;else{swap(nums[--right],nums[i]);}}}
};

2. 912. 排序数组

在这里插入图片描述

2.1 分析

可以先选择一个元素作为基准,把比它小的元素都放在它的左边,把它大的都放在右边,中间放的数就和它相等,这样数组就分为三个区间,递归找一下左边,再递归找一下右边,直到数组全部被排好。
在这里插入图片描述

为了减少时间复杂度,选取基准值的时候选取随机数。
在这里插入图片描述

2.2 代码

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;int k=getRandom(nums,l,r);int i=l,left=l-1,right=r+1;while(i<right){      if(nums[i]<k){swap(nums[++left],nums[i++]);}else if(nums[i]==k)i++;else{swap(nums[--right],nums[i]);}}qsort(nums,l,left);qsort(nums,right,r);}int getRandom(vector<int>& nums,int left,int right){int r=rand();return nums[r%(right-left+1)+left];}
};

3. 215. 数组中的第K个最大元素

在这里插入图片描述

3.1 分析

和上面那题一样,这里也将区间分三块。
随机选取一个基准元素k,根据这个基准元素将区间分三部分,左边都是小于k的,中间都是等于k的,有边都是大于k的。
题目要求找到的是第k大元素,那么在三个区域都有可以,但是如果确定这个第k大元素是在某一个区域的时候,那么剩下的两个区域就都不用考虑。
左边元素个数为a,中间为b,右边为c。
第一种如果在c区域,那么c大于等于k的,因为c区域放的是是大值区域,如果存在第k大的,那么最有可能就在c中,只需要c大于等于k就一定在。
在第二种情况找的时候,就说明第一种情况不存在,在中间的区域,那么就直接返回k就行,因为中间元素都是相等的。
第三种情况,前面两种情况都不存在,那么就在左边区间找,右边区域和中间区域都没有,那么找的就是第k-b-c大的元素。

在这里插入图片描述

3.2 代码

class Solution {
public:int findKthLargest(vector<int>& nums, int k) {srand(time(NULL));return qsort(nums, 0, nums.size() - 1,k);}int qsort(vector<int>& nums, int l, int r,int k){if(l==r)return nums[l];int key=getRandom(nums,l,r);int i=l,left=l-1,right=r+1;while(i<right){      if(nums[i]<key){swap(nums[++left],nums[i++]);}else if(nums[i]==key)i++;else{swap(nums[--right],nums[i]);}}//分情况讨论int c=r-right+1,b=right-left-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); }int getRandom(vector<int>& nums,int left,int right){int r=rand();return nums[r%(right-left+1)+left];}
};

4. LCR 159. 库存管理 III

在这里插入图片描述

4.1 分析

解法一:
可以直接排序,把前面的cnt个数重新放在一个vector表里面返回就行。

解法二:用快速选择算法
就是前面所提到的随机选择基准元素k,把数组分三个区间。
在这里插入图片描述
然后统计每一个区间的个数,此时就分为三种情况:
第一种情况:第k小,如果a>k就先从第一个区间找。
第二种情况:a+b大于等于k,那么就直接返回k就行,这个区间值都是相等的。
第三种情况:前面两种情况都不成立,说明这个k在右边这个区域,找k-a-b个元素就可以。

在这里插入图片描述

4.2 代码

解法一:

class Solution {
public:vector<int> inventoryManagement(vector<int>& stock, int cnt) {sort(stock.begin(),stock.end());vector<int> v;for(int i=0;i<cnt;i++){v.push_back(stock[i]);}return v;}
};

解法二:

class Solution {
public:vector<int> inventoryManagement(vector<int>& stock, int cnt) {srand(time(NULL));qsort(stock, 0, stock.size() - 1,cnt);return {stock.begin(),stock.begin()+cnt};}void qsort(vector<int>& stock, int l, int r,int k){if(l>=r)return;int key=getRandom(stock,l,r);int i=l,left=l-1,right=r+1;while(i<right){      if(stock[i]<key) swap(stock[++left],stock[i++]);else if(stock[i]==key)i++;else swap(stock[--right],stock[i]);}//分情况讨论int a=left-l+1,b=right-left-1;if(a>k)qsort(stock,l,left,k);else if(a+b>=k) return;else  qsort(stock,right,r,k-a-b); }int getRandom(vector<int>&stock,int left,int right){int r=rand();return stock[r%(right-left+1)+left];}};

有问题请指出,大家一起进步!!!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/308353.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

GitHub repository - Pulse - Contributors - Network

GitHub repository - Pulse - Contributors - Network 1. Pulse2. Contributors3. NetworkReferences 1. Pulse 显示该仓库最近的活动信息。该仓库中的软件是无人问津&#xff0c;还是在火热地开发之中&#xff0c;从这里可以一目了然。 2. Contributors 显示对该仓库进行过…

设备树的概念、设备树如何变成device、与driver的匹配

在平台总线驱动模型中资源和驱动已经从逻辑上和代码组织上进行了分离&#xff0c;但每次调整资源还是会涉及到内核&#xff0c;所以现在更加流行的是设备树方式。设备树的好处是通过独立于内核存在&#xff0c;这样如果设备上外设功能启用与否以及位置变动的话很多时候不用修改…

深入理解计算机网络分层结构

一、 为什么要分层&#xff1f; 计算机网络分层的主要目的是将复杂的网络通信过程分解为多个相互独立的层次&#xff0c;每个层次负责特定的功能。这样做有以下几个好处&#xff1a; 模块化设计&#xff1a;每个层次都有清晰定义的功能和接口&#xff0c;使得网络系统更易于设…

修复 Windows 上的 PyTorch 1.1 github 模型加载权限错误

问题: 在 Windows 计算机上执行示例 github 模型加载时,生成了 master.zip 文件的权限错误(请参阅下面的错误堆栈跟踪)。 错误堆栈跟踪: 在[4]中:en2de = torch.hub.load(pytorch/fairseq, transformer.wmt16.en-de, tokenizer=moses, bpe=subword_nmt) 下载:“https://…

【Java基础题型】矩阵的对角线求和

一、题目-矩阵 求一个33矩阵对角线元素之和。 输入格式 矩阵 输出格式 主对角线 副对角线 元素和 样例输入 1 2 3 1 1 1 3 2 1 样例输出 3 7 二、参考的知识 这里给大家送点英语单词&#xff0c;记得学习&#xff1a; p r i m a r y. adj.主要的&#xff1b;初…

谈谈我的软考高级考证之路(系统架构设计师篇)

系统架构设计师备考资料请移步 2023年软考高级系统架构设计师视频教程&#xff0c;推荐下载&#xff01;获取。 备考总体策略 • 总体策略&#xff1a;刷视频记笔记刷真题 • 备考时间&#xff1a;建议报完名之后&#xff0c;开始备考&#xff0c;大致2-3个月&#xff08;基础…

CNN-Transformer时间序列预测

部分代码&#xff1a; # CNN-Transformer class CNNTransformerEncoder(nn.Module):def __init__(self, input_features, transformer_encoder_heads,embedding_features, cnn_kernel_size, dim_feedforward_enc, n_encoder_layer):super(CNNTransformerEncoder, self).__init…

复旦新出!大规模语言模型:从理论到实践,书籍PDF分享

自2018年以来&#xff0c;包含Google、OpenAI、Meta、百度、华为等公司和研究机构都纷纷发布了包括BERT&#xff0c; GPT等在内多种模型&#xff0c;并在几乎所有自然语言处理任务中都表现出色。 今天给大家推荐一本大模型方面的书籍<大规模语言模型&#xff1a;从理论到实…

互联网轻量级框架整合之MyBatis核心组件

在看本篇内容之前&#xff0c;最好先理解一下Hibernate和MyBatis的本质区别&#xff0c;这篇Hibernate和MyBatis使用对比实例做了实际的代码级对比&#xff0c;而MyBatis作为更适合互联网产品的持久层首选必定有必然的原因 MyBatis核心组件 MyBatis能够成为数据持久层首选框&a…

Axure RP中的相关概念及高保真原型构建方法

1 Axure RP中概念介绍 对于构建高保真原型来说&#xff0c;需要知道事件&#xff08;Event&#xff09;、Case、Action等概念。Axure RP中给出这些概念&#xff0c;是为了方便原型的构建&#xff0c;尤其是高保真原型的构建。 事件&#xff08;Event&#xff09;是附着于控件…

[图解]DDD领域驱动设计伪创新-聚合根03

0 00:00:04,120 --> 00:00:07,267 上次我们说到这个Aggregate 1 00:00:07,267 --> 00:00:10,100 就是聚合体的问题 2 00:00:11,340 --> 00:00:16,170 说问题在&#xff0c;它是把重点放在结点上面 3 00:00:17,580 --> 00:00:18,160 4 00:00:18,470 --> 00:00…

selenium添加代理(有账号密码)

以下为各种尝试的记录&#xff0c;正确实现可直接参考最后一条&#xff01; 1&#xff0c;导入Proxy库来添加capabilities属性&#xff1a;可以访问网站&#xff0c;但ip还是本机ip from selenium import webdriver from selenium.webdriver.chrome.options import Options f…

C语言: 字符串函数(下)

片头 在上一篇中,我们介绍了字符串函数。在这一篇章中&#xff0c;我们将继续学习字符串函数&#xff0c;准备好了吗&#xff1f;开始咯&#xff01; 1.strncpy函数 1.1 strncpy函数的用法 strncpy是C语言中的一个字符串处理函数&#xff0c;它用于将一个字符串的一部分内容…

uniapp区分app、h5、小程序

APP端 标签内 <!-- #ifdef APP-PLUS --><view> APP端 </view> <!-- #endif --> JSCSS内 /*#ifdef APP-PLUS*/console.log(APP端) /*#endif*/ H5端 标签内 <!-- #ifdef H5 --><view> H5端 </view> <!-- #endif --> JSC…

18篇文章带你深入浅出了解亚组交互作用(p for Interaction)及可视化分析

交互作用效应(p for Interaction)在SCI文章中可以算是一个必杀技&#xff0c;几乎在高分的SCI中必出现&#xff0c;因为把人群分为亚组后再进行统计可以增强文章结果的可靠性&#xff0c;进行可视化后可以清晰的表明变量之间的关系。不仅如此&#xff0c;交互作用还可以使用来进…

HTML5学习记录

简介 超文本标记语言&#xff08;HyperText Markup Language&#xff0c;简称HTML&#xff09;&#xff0c;是一种用于创建网页的标准标记语言。 编辑器 下载传送门https://code.visualstudio.com/ 下载编辑器插件 标题 标题通过 <h1> - <h6> 标签进行定义。 …

【C++学习】C++11新特性(第一节)

文章目录 ♫一.文章前言♫二.C11新特性♫一.统一的列表初始化♫二.std::initializer_list♫三.声明♫四.decltype关键字♫五.nullptr♫六.新增加容器---静态数组array、forward_list以及unordered系列♫6.1unordered_map与unoredered_set♫6.2array♫6.3 forward_list&#xff…

深度学习体系结构——CNN, RNN, GAN, Transformers, Encoder-Decoder Architectures算法原理与应用

1. 卷积神经网络 卷积神经网络&#xff08;CNN&#xff09;是一种特别适用于处理具有网格结构的数据&#xff0c;如图像和视频的人工神经网络。可以将其视作一个由多层过滤器构成的系统&#xff0c;这些过滤器能够处理图像并从中提取出有助于进行预测的有意义特征。 设想你手…

计算机组成原理【CO】Ch2 数据的表示和应用

文章目录 大纲2.1 数制与编码2.2 运算方法和运算电路2.3 浮点数的表示和运算 【※】带标志加法器OFSFZFCF计算机怎么区分有符号数无符号数? 【※】存储排列和数据类型转换数据类型大小数据类型转换 进位计数制进制转换2的次幂 各种码的基本特性无符号整数的表示和运算带符号整…

(我的创作纪念日)[MySQL]数据库原理7——喵喵期末不挂科

希望你开心&#xff0c;希望你健康&#xff0c;希望你幸福&#xff0c;希望你点赞&#xff01; 最后的最后&#xff0c;关注喵&#xff0c;关注喵&#xff0c;关注喵&#xff0c;大大会看到更多有趣的博客哦&#xff01;&#xff01;&#xff01; 喵喵喵&#xff0c;你对我真的…