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

【优选算法】(第二十三篇)

目录

快速选择算法(medium)

题目解析

讲解算法原理

编写代码

最⼩的k个数(medium)

题目解析

讲解算法原理

编写代码


快速选择算法(medium)

题目解析

1.题目链接:. - 力扣(LeetCode)

2.题目描述

给定整数数组nums和整数k,请返回数组中第k个最⼤的元素。
请注意,你需要找的是数组排序后的第k个最⼤的元素,⽽不是第k个不同的元素。
你必须设计并实现时间复杂度为O(n)的算法解决此问题。
⽰例1:
输⼊:[3,2,1,5,6,4],k=2
输出:5
⽰例2:
输⼊:[3,2,3,1,2,4,5,5,6],k=4
输出:4

提⽰:
1<=k<=nums.length<=10^5
-10^4<=nums[i]<=10^4

讲解算法原理

解法(快速选择算法):
算法思路:
在快排中,当我们把数组「分成三块」之后: [l, left] [left + 1, right - 1] [right, r] ,我们可以通过计算每⼀个区间内元素的「个数」,进⽽推断出我们要找的元素是在「哪⼀个区间」⾥⾯。
那么我们可以直接去「相应的区间」去寻找最终结果就好了。

编写代码

c++算法代码:

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];// 1. 随机选择基准元素int key = getRandom(nums, l, r);// 2. 根据基准元素将数组分三块int left = l - 1, right = r + 1, i = l;while(i < right){if(nums[i] < key) swap(nums[++left], nums[i++]);else if(nums[i] == key) i++;else swap(nums[--right], nums[i]);}// 3. 分情况讨论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){return nums[rand() % (right - left + 1) + left];}
};

java算法代码:

class Solution
{public int findKthLargest(int[] nums, int k) {return qsort(nums, 0, nums.length - 1, k);}public int qsort(int[] nums, int l, int r, int k) {if(l == r) {return nums[l];}// 1. 按照随机选择的基准元素,将数组分三块int key = nums[new Random().nextInt(r - l + 1) + l];int left = l - 1, right = r + 1, i = l;while(i < right) {if(nums[i] < key) swap(nums, ++left, i++);else if(nums[i] == key) i++;else swap(nums, --right, i);}// 2. 分情况讨论int c = r - right + 1, b = right - left - 1;if(c >= k) return qsort(nums, right, r, k);else if(c + b >= k) return key;else return qsort(nums, l, left, k - b - c);}public void swap(int[] nums, int i, int j) {int t = nums[i];nums[i] = nums[j];nums[j] = t;}
}

最⼩的k个数(medium)

题目解析

1.题目链接:. - 力扣(LeetCode)

2.题目描述

输⼊整数数组arr,找出其中最⼩的k个数。例如,输⼊4、5、1、6、2、7、3、8这8个数字,则最⼩的4个数字是1、2、3、4。
⽰例1:
输⼊:arr=[3,2,1],k=2
输出:[1,2]或者[2,1]
⽰例2:
输⼊:arr=[0,1,2,1],k=1
输出:[0]

限制:
0<=k<=arr.length<=10000
0<=arr[i]<=10000

讲解算法原理

解法(快速选择算法):
算法思路:

在快排中,当我们把数组「分成三块」之后: [l, left] [left + 1, right - 1] [right, r] ,我们可以通过计算每⼀个区间内元素的「个数」,进⽽推断出最⼩的k个数在哪些区间⾥⾯。
那么我们可以直接去「相应的区间」继续划分数组即可。

编写代码

c++算法代码:

class Solution
{
public:vector<int> getLeastNumbers(vector<int>& nums, int k) {srand(time(NULL));qsort(nums, 0, nums.size() - 1, k);return {nums.begin(), nums.begin() + k};}void qsort(vector<int>& nums, int l, int r, int k){if(l >= r) return;// 1. 随机选择⼀个基准元素 + 数组分三块int key = getRandom(nums, l, r);int left = l - 1, right = r + 1, i = l;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]// 2. 分情况讨论int a = left - l + 1, b = right - left - 1;if(a > k) qsort(nums, l, left, k);else if(a + b >= k) return;else qsort(nums, right, r, k - a - b);}int getRandom(vector<int>& nums, int l, int r){return nums[rand() % (r - l + 1) + l];}
};

java算法代码:

class Solution
{public int[] getLeastNumbers(int[] nums, int k) {qsort(nums, 0, nums.length - 1, k);int[] ret = new int[k];for(int i = 0; i < k; i++)ret[i] = nums[i];return ret;}public void qsort(int[] nums, int l, int r, int k){if(l >= r) return;// 1. 随机选择⼀个基准元素 + 数组分三块int key = nums[new Random().nextInt(r - l + 1) + l];int left = l - 1, right = r + 1, i = l;while(i < right){if(nums[i] < key) swap(nums, ++left, i++);else if(nums[i] == key) i++;else swap(nums, --right, i);}// 2. 分类讨论int a = left - l + 1, b = right - left - 1;if(a > k) qsort(nums, l, left, k);else if(a + b >= k) return;else qsort(nums, right, r, k - a - b);}public void swap(int[] nums, int i, int j){int t = nums[i];nums[i] = nums[j];nums[j] = t;}
}

相关文章:

【优选算法】(第二十三篇)

目录 快速选择算法&#xff08;medium&#xff09; 题目解析 讲解算法原理 编写代码 最⼩的k个数&#xff08;medium&#xff09; 题目解析 讲解算法原理 编写代码 快速选择算法&#xff08;medium&#xff09; 题目解析 1.题目链接&#xff1a;. - 力扣&#xff08;L…...

Java.数据结构.HashSet

目录 1 基本概念 2 数据结构 3 常用操作 3.1 add(E e)&#xff1a;向HashSet中添加元素 3.2 remove(Object o)&#xff1a;从HashSet中移除元素 3.3 contains(Object o)&#xff1a;判断HashSet中是否包含指定元素 3.4 size()&#xff1a;返回HashSet中元素的个数 3.5 …...

关于懒惰学习与渴求学习的一份介绍

在这篇文章中&#xff0c;我将介绍些懒惰学习与渴求学习的算法例子&#xff0c;会介绍其概念、优缺点以及其python的运用。 一、渴求学习 1.1概念 渴求学习&#xff08;Eager Learning&#xff09;是指在训练阶段构建出复杂的模型&#xff0c;然后在预测阶段运用这个构建出的…...

sed 环境配置

参考项目来自这里&#xff1a; https://github.com/DCASE-REPO/DESED_task/tree/master/recipes/dcase2023_task4_baseline 1. 更新自己的 conda 避免一些包在旧的conda 环境中不存在&#xff1b; conda update conda使用conda 指定安装 对应版本 # CUDA 11.7 conda instal…...

黑神话:仙童,数据库自动反射魔法棒

黑神话&#xff1a;仙童&#xff0c;数据库自动反射魔法棒 Golang 通用代码生成器仙童发布了最新版本电音仙女尝鲜版十一及其介绍视频&#xff0c;视频请见&#xff1a;https://www.bilibili.com/video/BV1ET4wecEBk/ 此视频介绍了使用最新版的仙童代码生成器&#xff0c;将 …...

香江电器冲刺港交所上市:投资方提前撤资退出,因对赌协议而赔偿

近日&#xff0c;湖北香江电器股份有限公司&#xff08;X.J. ELECTRICS (HU BEI) CO., LTD&#xff0c;下称“香江电器”&#xff09;披露招股书&#xff0c;准备在港交所主板上市&#xff0c;国金证券为其独家保荐人。据贝多财经了解&#xff0c;香江电器曾计划在A股上市&…...

SpringSecurity实现自定义登录接口

SpringSecurity实现自定义登录接口 1、配置类 ConfigClazz&#xff08;SpringSecuriey的&#xff09; //首先就是要有一个配置类Resourceprivate DIYUsernamePasswordAuthenticationFilter diyUsernamePasswordAuthenticationFilter;/*SpringSecurity配置*/Beanpublic Securit…...

深度解析:Tkinter 界面布局与优化技巧

目录 深度解析&#xff1a;Tkinter 界面布局与优化技巧1. Tkinter 布局管理简介如何选择合适的布局管理器 2. pack() 布局管理详解嵌套布局 3. grid() 布局管理详解行列合并 4. place() 精确布局详解5. Tkinter 界面优化技巧自适应布局响应式布局资源管理 6. 项目示例&#xff…...

RCE_无回显

<aside> &#x1f4a1; 无回显 </aside> 写文件 **curl -o shell.php <http://xxxxxx.txt> wget -O shell.php <http://xxxxxx.txt>**请求带出 **curl <http://requestbin.net/r/1kiej1p1?pcat> /flag|base64 curl xxd -p /flag.xxxxxx.dnslo…...

文心一言智能体——绿色生活管家

最近&#xff0c;我在参加文心一言智能体大赛&#xff0c;这是我的智能体地址绿色生活管家&#xff0c;点击即可访问&#xff0c;大家可以去向我的智能体提问&#xff0c;提五个问题左右即可&#xff0c;真的非常感谢大家&#xff01;好人一生平安&#x1f33c;&#x1f33c;&a…...

无人机(自组穿越机,航模)-芯片选型

飞控MCU: 型号尺寸子型号参数规格备注STM325*532位ARM Cortex-M3 CPU&#xff0c;72MHz&#xff0c;256KB Flash&#xff0c;20KB RAMLQFP 48F33*332位ARM Cortex-M4 CPU&#xff0c;72MHz&#xff0c;256KB Flash&#xff0c;40KB RAMMPU6050F45*532位ARM Cortex-M4 CPU&…...

[Cocoa]_[初级]_[绘制文本如何设置断行效果]

场景 在开发Cocoa程序时&#xff0c;表格NSTableView是经常使用的控件。其基于View Base的视图单元格模式就是使用NSCell或其子类来控制每个单元格的呈现。当一个单元格里的文字过多时&#xff0c;需要截断超出宽度的文字&#xff0c;怎么实现&#xff1f; 说明 Cocoa下的文本…...

IPS和IDS有啥区别

在网络安全领域&#xff0c;入侵检测系统 (IDS) 和入侵防御系统 (IPS) 是两种关键的技术&#xff0c;旨在保护网络免受各种威胁。这两者尽管名字相似&#xff0c;但在功能、配置、以及应用场景等方面都有着显著的差异。 入侵检测系统 (IDS) IDS 是一种被动监控系统&#xff0c…...

c基础面试题

1.static和const的作用 static意为静态的&#xff0c;在C语言中可以修饰变量。如果是全局变量则只能在当前文件范围访问。 如果是函数内的局部变量则延长生命周期到整个程序。这意味着如果函数被多次调用&#xff0c;这个变量不会被重新初始化&#xff0c;而是保留上次调用结…...

选择最佳HR系统_6款产品评测与推荐

本文盘点了ZohoPeople、SAPSuccessFactors等六款主流HRMS&#xff0c;各系统各具特色&#xff0c;如ZohoPeople的全球化云管理、SAP的高定制化、Workday的实时数据分析等&#xff0c;适合不同规模企业需求&#xff0c;建议企业试用后决策。 一、Zoho People Zoho People 是一个…...

Latex技巧——参考文献中加入url和doi

有的期刊要求在参考文献里加入url或者doi, 例如下图中蓝色的字体。 在bib里编辑为下图中note行&#xff0c;也就是利用\href命令。\href后第一个{}内为网址&#xff0c;第二个{}为在参考文献中显示的蓝色文字。一般来说&#xff0c;两个{}内的文字相同。若遇到有些网址有下划线…...

安卓WPS Office v18.13.0高级版

软件介绍 WPS Office&#xff0c;金山WPS移动版&#xff0c;使用人数最多的移动办公软件套件。独有手机阅读模式&#xff0c;字体清晰翻页流畅&#xff1b;完美支持文字&#xff0c;表格&#xff0c;演示&#xff0c;PDF等51种文档格式&#xff1b;新版本具有海量精美模版及高…...

【C++力扣】917.仅仅反转字母|387.字符串中第一个唯一字符|415.字符串相加

✨ Blog’s 主页: 白乐天_ξ( ✿&#xff1e;◡❛) &#x1f308; 个人Motto&#xff1a;他强任他强&#xff0c;清风拂山冈&#xff01; &#x1f525; 所属专栏&#xff1a;C深入学习笔记 &#x1f4ab; 欢迎来到我的学习笔记&#xff01; 一、917.仅仅反转字母 1.1 题目描述…...

RxSwift系列(四)异常处理和调试操作

一、异常处理 1.catchErrorJustReturn 当遇到 error 事件的时候&#xff0c;就返回指定的值&#xff0c;然后结束。 enum MyError: Error {case Acase B }let disposeBag DisposeBag()let sequenceThatFails PublishSubject<String>()sequenceThatFails.catchErrorJ…...

Excel基础:电子表格Excel的使用技巧合集

一、内容 1.表格下拉框选择内容...

大学生职业发展与就业创业指导教学评价

这里是引用 作为软工2203/2204班的学生&#xff0c;我们非常感谢您在《大学生职业发展与就业创业指导》课程中的悉心教导。这门课程对我们即将面临实习和就业的工科学生来说至关重要&#xff0c;而您认真负责的教学态度&#xff0c;让课程的每一部分都充满了实用价值。 尤其让我…...

Device Mapper 机制

Device Mapper 机制详解 Device Mapper&#xff08;简称 DM&#xff09;是 Linux 内核中的一套通用块设备映射框架&#xff0c;为 LVM、加密磁盘、RAID 等提供底层支持。本文将详细介绍 Device Mapper 的原理、实现、内核配置、常用工具、操作测试流程&#xff0c;并配以详细的…...

初学 pytest 记录

安装 pip install pytest用例可以是函数也可以是类中的方法 def test_func():print()class TestAdd: # def __init__(self): 在 pytest 中不可以使用__init__方法 # self.cc 12345 pytest.mark.api def test_str(self):res add(1, 2)assert res 12def test_int(self):r…...

虚拟电厂发展三大趋势:市场化、技术主导、车网互联

市场化&#xff1a;从政策驱动到多元盈利 政策全面赋能 2025年4月&#xff0c;国家发改委、能源局发布《关于加快推进虚拟电厂发展的指导意见》&#xff0c;首次明确虚拟电厂为“独立市场主体”&#xff0c;提出硬性目标&#xff1a;2027年全国调节能力≥2000万千瓦&#xff0…...

Go语言多线程问题

打印零与奇偶数&#xff08;leetcode 1116&#xff09; 方法1&#xff1a;使用互斥锁和条件变量 package mainimport ("fmt""sync" )type ZeroEvenOdd struct {n intzeroMutex sync.MutexevenMutex sync.MutexoddMutex sync.Mutexcurrent int…...

系统掌握PyTorch:图解张量、Autograd、DataLoader、nn.Module与实战模型

本文较长&#xff0c;建议点赞收藏&#xff0c;以免遗失。更多AI大模型应用开发学习视频及资料&#xff0c;尽在聚客AI学院。 本文通过代码驱动的方式&#xff0c;系统讲解PyTorch核心概念和实战技巧&#xff0c;涵盖张量操作、自动微分、数据加载、模型构建和训练全流程&#…...

上位机开发过程中的设计模式体会(1):工厂方法模式、单例模式和生成器模式

简介 在我的 QT/C 开发工作中&#xff0c;合理运用设计模式极大地提高了代码的可维护性和可扩展性。本文将分享我在实际项目中应用的三种创造型模式&#xff1a;工厂方法模式、单例模式和生成器模式。 1. 工厂模式 (Factory Pattern) 应用场景 在我的 QT 项目中曾经有一个需…...

【深度学习新浪潮】什么是credit assignment problem?

Credit Assignment Problem(信用分配问题) 是机器学习,尤其是强化学习(RL)中的核心挑战之一,指的是如何将最终的奖励或惩罚准确地分配给导致该结果的各个中间动作或决策。在序列决策任务中,智能体执行一系列动作后获得一个最终奖励,但每个动作对最终结果的贡献程度往往…...

uni-app学习笔记三十五--扩展组件的安装和使用

由于内置组件不能满足日常开发需要&#xff0c;uniapp官方也提供了众多的扩展组件供我们使用。由于不是内置组件&#xff0c;需要安装才能使用。 一、安装扩展插件 安装方法&#xff1a; 1.访问uniapp官方文档组件部分&#xff1a;组件使用的入门教程 | uni-app官网 点击左侧…...

Spring AOP代理对象生成原理

代理对象生成的关键类是【AnnotationAwareAspectJAutoProxyCreator】&#xff0c;这个类继承了【BeanPostProcessor】是一个后置处理器 在bean对象生命周期中初始化时执行【org.springframework.beans.factory.config.BeanPostProcessor#postProcessAfterInitialization】方法时…...