当前位置: 首页 > 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…...

Python爬虫实战:研究MechanicalSoup库相关技术

一、MechanicalSoup 库概述 1.1 库简介 MechanicalSoup 是一个 Python 库,专为自动化交互网站而设计。它结合了 requests 的 HTTP 请求能力和 BeautifulSoup 的 HTML 解析能力,提供了直观的 API,让我们可以像人类用户一样浏览网页、填写表单和提交请求。 1.2 主要功能特点…...

MySQL 隔离级别:脏读、幻读及不可重复读的原理与示例

一、MySQL 隔离级别 MySQL 提供了四种隔离级别,用于控制事务之间的并发访问以及数据的可见性,不同隔离级别对脏读、幻读、不可重复读这几种并发数据问题有着不同的处理方式,具体如下: 隔离级别脏读不可重复读幻读性能特点及锁机制读未提交(READ UNCOMMITTED)允许出现允许…...

线程同步:确保多线程程序的安全与高效!

全文目录&#xff1a; 开篇语前序前言第一部分&#xff1a;线程同步的概念与问题1.1 线程同步的概念1.2 线程同步的问题1.3 线程同步的解决方案 第二部分&#xff1a;synchronized关键字的使用2.1 使用 synchronized修饰方法2.2 使用 synchronized修饰代码块 第三部分&#xff…...

Go 并发编程基础:通道(Channel)的使用

在 Go 中&#xff0c;Channel 是 Goroutine 之间通信的核心机制。它提供了一个线程安全的通信方式&#xff0c;用于在多个 Goroutine 之间传递数据&#xff0c;从而实现高效的并发编程。 本章将介绍 Channel 的基本概念、用法、缓冲、关闭机制以及 select 的使用。 一、Channel…...

Elastic 获得 AWS 教育 ISV 合作伙伴资质,进一步增强教育解决方案产品组合

作者&#xff1a;来自 Elastic Udayasimha Theepireddy (Uday), Brian Bergholm, Marianna Jonsdottir 通过搜索 AI 和云创新推动教育领域的数字化转型。 我们非常高兴地宣布&#xff0c;Elastic 已获得 AWS 教育 ISV 合作伙伴资质。这一重要认证表明&#xff0c;Elastic 作为 …...

02.运算符

目录 什么是运算符 算术运算符 1.基本四则运算符 2.增量运算符 3.自增/自减运算符 关系运算符 逻辑运算符 &&&#xff1a;逻辑与 ||&#xff1a;逻辑或 &#xff01;&#xff1a;逻辑非 短路求值 位运算符 按位与&&#xff1a; 按位或 | 按位取反~ …...

多元隐函数 偏导公式

我们来推导隐函数 z z ( x , y ) z z(x, y) zz(x,y) 的偏导公式&#xff0c;给定一个隐函数关系&#xff1a; F ( x , y , z ( x , y ) ) 0 F(x, y, z(x, y)) 0 F(x,y,z(x,y))0 &#x1f9e0; 目标&#xff1a; 求 ∂ z ∂ x \frac{\partial z}{\partial x} ∂x∂z​、 …...

[特殊字符] 手撸 Redis 互斥锁那些坑

&#x1f4d6; 手撸 Redis 互斥锁那些坑 最近搞业务遇到高并发下同一个 key 的互斥操作&#xff0c;想实现分布式环境下的互斥锁。于是私下顺手手撸了个基于 Redis 的简单互斥锁&#xff0c;也顺便跟 Redisson 的 RLock 机制对比了下&#xff0c;记录一波&#xff0c;别踩我踩过…...

算法—栈系列

一&#xff1a;删除字符串中的所有相邻重复项 class Solution { public:string removeDuplicates(string s) {stack<char> st;for(int i 0; i < s.size(); i){char target s[i];if(!st.empty() && target st.top())st.pop();elsest.push(s[i]);}string ret…...

Java多线程实现之Runnable接口深度解析

Java多线程实现之Runnable接口深度解析 一、Runnable接口概述1.1 接口定义1.2 与Thread类的关系1.3 使用Runnable接口的优势 二、Runnable接口的基本实现方式2.1 传统方式实现Runnable接口2.2 使用匿名内部类实现Runnable接口2.3 使用Lambda表达式实现Runnable接口 三、Runnabl…...