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

【剑指offer】53. 最小的k个数(java选手)(优先队列+快排+快速选择)

题目链接

题目链接
力扣题目链接

题目描述

输入 n个整数,找出其中最小的 k 个数。

注意:
输出数组内元素请按从小到大顺序排序;
数据范围
1≤k≤n≤1000

样例
输入:[1,2,3,4,5,6,7,8] , k=4
输出:[1,2,3,4]

题目分析

  • 排序算法

题解

优先队列-小根堆

  • 用小根堆

将所有元素都放入小根堆中,就相当于堆元素进行了排序。
然后依次从优先队列的首部(最小的位置)开始取元素,取k个为止

注意啦!
这是优先队列(升序排列)实现的小根堆
也就是每次peek取出的元素都是当前优先队列中最小的!

class Solution {public List<Integer> getLeastNumbers_Solution(int[] input, int k) {// 优先队列(升序),小根堆,根是最小的【peek取出的元素是最小的】PriorityQueue<Integer> pq = new PriorityQueue<>((a, b)->a-b);for(int i = 0; i < input.length; i ++){pq.add(input[i]);}List<Integer> list = new ArrayList<>();for(int i = 0; i < k; i ++){list.add(pq.poll());}return list;}
}

优先队列-大根堆

  • 从大到小排序,首部元素是最大的
  • 只存放k个整数,如果超过这个值之后,遍历的元素与首部元素小才插入(因为要找前k个最小的元素)
  • 遍历优先队列,不停的在list首部插入值(因为是大根堆,所以队列首部的元素是最大的)
class Solution {public List<Integer> getLeastNumbers_Solution(int[] input, int k) {// 大根堆,堆中只存放k个整数,超过这个k值后,如果元素比peek得到的值小,插入// 优先队列从大到小排序,逆序PriorityQueue<Integer> pq = new PriorityQueue<>((a, b)-> b - a);for(int i = 0; i < input.length; i ++){if(pq.size() >= k){if(pq.peek() > input[i]){pq.poll();pq.add(input[i]);}}else{pq.add(input[i]);}}List<Integer> list = new ArrayList<>();for(int i = 0; i < k; i ++){list.add(0, pq.poll());}return list;}
}

快排

写法1:

class Solution {public int[] smallestK(int[] arr, int k) {sort(arr, 0, arr.length - 1);int[] res = new int[k];for(int i = 0; i < k; i ++){res[i] = arr[i];}return res;}public void sort(int[] arr, int left, int right){// 只有最后一个元素if(left >= right) return;// 基准int base = arr[left];int i = left, j = right;while(i < j){while(i < j && arr[j] > base){j--;}if(i < j){arr[i] = arr[j];i ++;}while(i < j && arr[i] < base){i ++;}if(i < j){arr[j] = arr[i];j --;}}arr[i] = base;sort(arr, left, i - 1);sort(arr, i + 1, right);}
}

写法2:

class Solution {public int[] smallestK(int[] arr, int k) {sort(arr, 0, arr.length - 1);int[] res = new int[k];for(int i = 0; i < k; i ++){res[i] = arr[i];}return res;}public void sort(int[] arr, int left, int right){// 只有最后一个元素if(left >= right) return;// 基准int base = arr[(left+right)/2];int i = left-1, j = right+1;while(i < j){do i++; while(arr[i] < base);do j--; while(arr[j] > base);if(i < j){int temp = arr[i];arr[i] = arr[j];arr[j] = temp;}}sort(arr, left, j);sort(arr, j + 1, right);}
}

快速选择

找第k个元素

class Solution {public int findKthLargest(int[] nums, int k) {// 需要数组中下标为need的元素int need = nums.length - k;return sort(nums, 0, nums.length - 1, need);}public int sort(int[] nums, int left, int right, int k) {if(left == right) return nums[left];int base = nums[(left + right) / 2];int i = left - 1, j = right + 1;while (i < j) {do i++; while (nums[i] < base);do j--; while (nums[j] > base);if (i < j) {int temp = nums[i];nums[i] = nums[j];nums[j] = temp;}}if(j >= k) return sort(nums, left, j, k);else return sort(nums, j + 1, right, k);}
}

注意!边界

if(j >= k) return sort(nums, left, j, k);
else return sort(nums, j + 1, right, k);

相关文章:

【剑指offer】53. 最小的k个数(java选手)(优先队列+快排+快速选择)

题目链接 题目链接 力扣题目链接 题目描述 输入 n个整数&#xff0c;找出其中最小的 k 个数。 注意&#xff1a; 输出数组内元素请按从小到大顺序排序; 数据范围 1≤k≤n≤1000 样例 输入&#xff1a;[1,2,3,4,5,6,7,8] , k4 输出&#xff1a;[1,2,3,4] 题目分析 排序算法…...

带有GUI界面的电机故障诊断(MSCNN-BILSTM-ATTENTION模型,TensorFlow框架,有中文注释,带有六种结果可视化)

本次创作最主要是在MSCNN-BILSTM-ATTENTION模型&#xff08;可轻松替换为其它模型&#xff09;基础上&#xff0c;搭建GUI测试界面&#xff0c;方便对你想要测试的数据的进行测试&#xff0c;同时进行了全面的结果可视化&#xff1a;1.训练集和测试集的准确率曲线&#xff0c;2…...

【技术栈】Spring Cache 简化 Redis 缓存使用

​ SueWakeup 个人主页&#xff1a;SueWakeup 系列专栏&#xff1a;学习技术栈 个性签名&#xff1a;保留赤子之心也许是种幸运吧 ​ 本文封面由 凯楠&#x1f4f8; 友情提供 目录 本栏传送门 1. Spring Cache 介绍 2. Spring Cache 常用注解 注&#xff1a;手机端浏览本文章…...

解决wrap_socket() got an unexpected keyword argument ‘ciphers‘

看报错本以为是一个简单的传参问题&#xff0c;没想到查到盘丝洞。 # 报错信息 wrap_socket() got an unexpected keyword argument ciphers# 报错代码段 _exception_handler() def connect(self):u"""连接MySQL数据库"""self.config_connect_a…...

【力扣hot100】128.最长连续序列

给定一个未排序的整数数组 nums &#xff0c;找出数字连续的最长序列&#xff08;不要求序列元素在原数组中连续&#xff09;的长度。 请你设计并实现时间复杂度为 O(n) 的算法解决此问题。 示例 1&#xff1a; 输入&#xff1a;nums [100,4,200,1,3,2] 输出&#xff1a;4 解…...

css的text-shadow详解

CSS的text-shadow属性用于为文本添加阴影效果&#xff0c;以增强文本的立体感和印刷品质感。该属性可以接受多个值&#xff0c;每个值通过空格分隔&#xff0c;以定义阴影的各个方面。以下是text-shadow属性的详细介绍&#xff1a; 阴影颜色 (Color): 这是阴影的颜色值。它可以…...

Qt 利用共享内存实现一次只能启动一个程序(单实例运行)

Qt 利用共享内存实现一次只能启动一个程序 文章目录 Qt 利用共享内存实现一次只能启动一个程序摘要利用共享内存实现一次只能启动一个程序示例代码 关键字&#xff1a; Qt、 unique、 单一、 QSharedMemory、 共享内存 摘要 今天接着在公司搞我的屎山代码&#xff0c;按照…...

【生活知识-茶叶】

生活知识-茶叶 茶 茶 茶叶分类代表茶名功效绿茶龙井碧螺春 毛峰清热解毒、降脂减肥、提神醒脑、改善肝功能、减轻肝脏负担乌龙茶铁观音武夷岩茶冻顶乌龙茶清心明目、提神醒脑、促进新陈代谢、维护肝脏健康白茶白毫银针白牡丹贡眉清热降火、抗氧化、保护心血管、提高免疫力黄茶…...

[AIGC] 在Spring Boot中指定请求体格式

在使用Spring Boot开发Web应用的时候&#xff0c;我们经常会遇到需要接收并处理HTTP请求的情况。一个HTTP请求通常包括一个请求行、若干请求头和一个请求体。请求体在POST和PUT请求中特别重要&#xff0c;因为它通常用于向服务器传递数据。 文章目录 创建并使用一个Java Bean指…...

4核16G服务器租用优惠价格,26.52元1个月,半年149元

阿里云4核16G服务器优惠价格26.52元1个月、79.56元3个月、149.00元半年&#xff0c;配置为阿里云服务器ECS经济型e实例ecs.e-c1m4.xlarge&#xff0c;4核16G、按固定带宽 10Mbs、100GB ESSD Entry系统盘&#xff0c;活动链接 aliyunfuwuqi.com/go/aliyun 活动链接打开如下图&a…...

2024 Mazing 3 中文版新功能介绍Windows and macOS

iMazing 3中文版(ios设备管理软件)是一款管理苹果设备的软件&#xff0c; Windows 平台上的一款帮助用户管理 IOS 手机的应用程序。iMazing中文版与苹果设备连接后&#xff0c;可以轻松传输文件&#xff0c;浏览保存信息等&#xff0c;软件功能非常强大&#xff0c;界面简洁明晰…...

npm设置淘宝镜像

使用npm安装依赖时很慢&#xff0c;可以设置淘宝镜像&#xff0c;2024年1月更换了新域名。 cmd在终端中做以下操作&#xff1a; 检测现在的镜像地址 npm config get registry如果不是淘宝最新的镜像地址&#xff0c;更换为 // 清空缓存 npm cache clean --force // 切换新源…...

现代卷积神经网络

深度卷积神经网络&#xff08;AlexNet&#xff09; 经典机器学习的流水线&#xff1a; ①获取一个有趣的数据集&#xff1b; ②根据光学、几何学&#xff0c;手动对特征数据集进行预处理&#xff1b; ③通过标准的特征提取算法&#xff0c;如SIFT&#xff08;尺度不变特征变…...

【wubuntu】披着Win11皮肤主题的Ubuntu系统

wubuntu - 一款外观类似于 Windows 的 Linux 操作系统&#xff0c;没有任何硬件限制。以下是官方的描述 Wubuntu is an operating system based on Ubuntu LTS that has a similar appearance to Windows using the open-source themes. Wubuntu also comes with a set of adva…...

Kubernetes自动化配置部署

在新建工程中&#xff0c;使用k8s的devops服务&#xff0c;自动化部署项目 1、在搭建好k8s的集群中&#xff0c;确认已开启devops服务&#xff1b; 2、新建Maven项目之后&#xff0c;创建dockerfile、deploy和Jenkins文件 例如&#xff1a; Dockerfile FROM bairong.k8s.m…...

2024年奥莱利科技趋势报告解析

2024年O’Reilly技术趋势报告解读 概述 在快速发展的技术领域&#xff0c;跟上最新趋势对行业内的任何人来说都至关重要。2024年O’Reilly技术趋势报告在此方面提供了关键的指导&#xff0c;全面概述了最重要的技术进步和模式。该年度报告基于O’Reilly著名在线学习平台280万…...

算法打卡Day14

今日任务&#xff1a; 1&#xff09;104.二叉树的最大深度 2&#xff09;559.n叉树的最大深度 3&#xff09;111.二叉树的最小深度 4&#xff09;222.完全二叉树的节点个数 104.二叉树的最大深度 题目链接&#xff1a;104. 二叉树的最大深度 - 力扣&#xff08;LeetCode&#…...

Android Kotlin版封装EventBus

文章目录 Android Kotlin版封装EventBus代码封装添加依赖库定义消息类定义常量值定义注解定义工具类 使用在Activity中在Fragment中发送事件 源码下载 Android Kotlin版封装EventBus 代码封装 添加依赖库 implementation("org.greenrobot:eventbus:3.3.1")定义消息…...

VUE父子组件的传参问题

1.父组件向子组件传参 1&#xff09;这是一个父组件 //这是一个父组件 <div> <port :port-List"portList" ></port> </div> //port 这是子组件的名称export default{components: {},props: {},data() {return{portList:,}},computed: {}…...

四、C#希尔排序算法

简介 希尔排序简单的来说就是一种改进的插入排序算法&#xff0c;它通过将待排序的元素分成若干个子序列&#xff0c;然后对每个子序列进行插入排序&#xff0c;最终逐步缩小子序列的间隔&#xff0c;直到整个序列变得有序。希尔排序的主要思想是通过插入排序的优势&#xff0…...

XCTF-web-easyupload

试了试php&#xff0c;php7&#xff0c;pht&#xff0c;phtml等&#xff0c;都没有用 尝试.user.ini 抓包修改将.user.ini修改为jpg图片 在上传一个123.jpg 用蚁剑连接&#xff0c;得到flag...

在四层代理中还原真实客户端ngx_stream_realip_module

一、模块原理与价值 PROXY Protocol 回溯 第三方负载均衡&#xff08;如 HAProxy、AWS NLB、阿里 SLB&#xff09;发起上游连接时&#xff0c;将真实客户端 IP/Port 写入 PROXY Protocol v1/v2 头。Stream 层接收到头部后&#xff0c;ngx_stream_realip_module 从中提取原始信息…...

UR 协作机器人「三剑客」:精密轻量担当(UR7e)、全能协作主力(UR12e)、重型任务专家(UR15)

UR协作机器人正以其卓越性能在现代制造业自动化中扮演重要角色。UR7e、UR12e和UR15通过创新技术和精准设计满足了不同行业的多样化需求。其中&#xff0c;UR15以其速度、精度及人工智能准备能力成为自动化领域的重要突破。UR7e和UR12e则在负载规格和市场定位上不断优化&#xf…...

MySQL 8.0 事务全面讲解

以下是一个结合两次回答的 MySQL 8.0 事务全面讲解&#xff0c;涵盖了事务的核心概念、操作示例、失败回滚、隔离级别、事务性 DDL 和 XA 事务等内容&#xff0c;并修正了查看隔离级别的命令。 MySQL 8.0 事务全面讲解 一、事务的核心概念&#xff08;ACID&#xff09; 事务是…...

如何应对敏捷转型中的团队阻力

应对敏捷转型中的团队阻力需要明确沟通敏捷转型目的、提升团队参与感、提供充分的培训与支持、逐步推进敏捷实践、建立清晰的奖励和反馈机制。其中&#xff0c;明确沟通敏捷转型目的尤为关键&#xff0c;团队成员只有清晰理解转型背后的原因和利益&#xff0c;才能降低对变化的…...

ThreadLocal 源码

ThreadLocal 源码 此类提供线程局部变量。这些变量不同于它们的普通对应物&#xff0c;因为每个访问一个线程局部变量的线程&#xff08;通过其 get 或 set 方法&#xff09;都有自己独立初始化的变量副本。ThreadLocal 实例通常是类中的私有静态字段&#xff0c;这些类希望将…...

简约商务通用宣传年终总结12套PPT模版分享

IOS风格企业宣传PPT模版&#xff0c;年终工作总结PPT模版&#xff0c;简约精致扁平化商务通用动画PPT模版&#xff0c;素雅商务PPT模版 简约商务通用宣传年终总结12套PPT模版分享:商务通用年终总结类PPT模版https://pan.quark.cn/s/ece1e252d7df...

ABAP设计模式之---“Tell, Don’t Ask原则”

“Tell, Don’t Ask”是一种重要的面向对象编程设计原则&#xff0c;它强调的是对象之间如何有效地交流和协作。 1. 什么是 Tell, Don’t Ask 原则&#xff1f; 这个原则的核心思想是&#xff1a; “告诉一个对象该做什么&#xff0c;而不是询问一个对象的状态再对它作出决策。…...

年度峰会上,抖音依靠人工智能和搜索功能吸引广告主

上周早些时候举行的第五届年度TikTok World产品峰会上&#xff0c;TikTok推出了一系列旨在增强该应用对广告主吸引力的功能。 新产品列表的首位是TikTok Market Scope&#xff0c;这是一个全新的分析平台&#xff0c;为广告主提供整个考虑漏斗的全面视图&#xff0c;使他们能够…...

PCA笔记

✅ 问题本质&#xff1a;为什么让矩阵 TT 的行列式为 1&#xff1f; 这个问题通常出现在我们对数据做**线性变换&#xff08;旋转/缩放&#xff09;**的时候&#xff0c;比如在 PCA 中把数据从原始坐标系变换到主成分方向时。 &#x1f4cc; 回顾一下背景 在 PCA 中&#xff…...