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

在做题中学习(79):最小K个数

解法:快速选择算法

说明:堆排序也是经典解决问题的算法,但时间复杂度为:O(NlogK),K为k个元素

而将要介绍的快速选择算法的时间复杂度为: O(N)

先看我的前两篇文章,分别学习:数组分三块,随机选择基准值的思想。会的话直接看就完事了

解惑:

1.a,b,c是什么意思?

        a,b,c分别是<key, = key, >key 所代表的区间中值的个数

2.如何判断?

        看落在哪个区间,a区间全是<key的,所以如果落在这个区间,说明k就在a这个区间,因此就只在这个区间递归即可。

        而如果 a + b >=k 说明,k > a了也就是说不仅在a区间,一定也包含b这个区间,而b都是= key的,所以此时直接返回即可,无需继续递归。

        如果都不是,说明k > a + b了,所以肯定也落进了c区间,而因为现在我们跳过了 a+b 个元素,所以要找的其实是剩下的k - b - c个元素!继续递归即可。

3.返回值

        函数的返回值要求是一个vector,而经过上面的分析,k个元素绝对是在一个区间中的,所以即便递归结束后数组是乱序,只要从[0,k]大小的区间内所有值都符合最小的k个元素,题目也说了可以以任意顺序返回,那结果就是直接返回递归后的[nums.begin(),nums.begin()+k]即可。

附上完整代码:

class Solution 
{
public:vector<int> smallestK(vector<int>& nums, int k) {srand(time(nullptr));qselect(nums,0,nums.size()-1,k);return {nums.begin(),nums.begin() + k};}void qselect(vector<int>& nums,int l,int r,int k){if(l >= r)return ;int key = GetRandomkey(nums,l,r);int left = l-1,right = r+1;for(int i = l;i<nums.size();){if(nums[i] < key)swap(nums[++left],nums[i++]);else if(nums[i] == key)i++;else if(nums[i] > key){if(i == right)break;swap(nums[--right],nums[i]);}}int a = left - l + 1,b = right - left - 1;if(a >= k)return qselect(nums,l,left,k);else if(a + b >=k)return;else return qselect(nums,right,r,k - a - b);}int GetRandomkey(vector<int>& nums,int l,int r){int random = rand();return nums[random % (r - l + 1) + l];}};
http://www.lryc.cn/news/499964.html

相关文章:

  • spark3 sql优化:同一个表关联多次,优化方案
  • JavaWeb学习(4)(四大域、HttpSession原理(面试)、SessionAPI、Session实现验证码功能)
  • Ubuntu22.04系统源码编译OpenCV 4.10.0(包含opencv_contrib)
  • 【Unity高级】在编辑器中如何让物体围绕一个点旋转固定角度
  • 2024.11.29——[HCTF 2018]WarmUp 1
  • AGameModeBase和游戏模式方法
  • Swift 扩展
  • 【NebulaGraph】官方查询语言nGQL教程1 (四)
  • 阿里云负载均衡SLB实践
  • 鸿蒙技术分享:❓❓[鸿蒙应用开发]怎么更好的管理模块生命周期?
  • 深度解析 Ansible:核心组件、配置、Playbook 全流程与 YAML 奥秘(上)
  • LabVIEW气缸摩擦力测试系统
  • Leetcode. 688骑士在棋盘上的概率
  • TCP/IP 协议栈高效可靠的数据传输机制——以 Linux 4.19 内核为例
  • Ubuntu22.04搭建LAMP环境(linux服务器学习笔记)
  • 鸿蒙面试---1208
  • java基础教程第16篇( 正则表达式)
  • Docker部署的gitlab升级的详细步骤(升级到17.6.1版本)
  • 【如何制定虚拟货币的补仓策略并计算回本和盈利】
  • 给图像去除水印攻
  • Linux之封装线程库和线程的互斥
  • PH热榜 | 2024-12-08
  • LeetCode刷题day20——贪心
  • CCF编程能力等级认证GESP—C++3级—20241207
  • Microi 吾码:大数据浪潮中的智能领航者
  • Lua语言入门 - Lua 数组
  • gulp应该怎么用,前端批量自动化替换文件
  • 石岩湿地公园的停车场收费情况
  • A7157 基于Java+SSM+mysql+jsp的医院挂号系统的设计与实现 源码 文档 配置 全套资料
  • 数据处理与统计分析——11-Pandas-Seaborn可视化