【剑指 Offer 40】最小的k个数
题目:
输入整数数组 arr ,找出其中最小的 k 个数。例如,输入 4、5、1、6、2、7、3、8 这 8 个数字,则最小的 4 个数字是 1、2、3、4。
示例:
输入:arr = [3,2,1], k = 2
输出:[1,2] 或者 [2,1]
输入:arr = [0,1,2,1], k = 1
输出:[0]
思考:
-
找到一个数组中最小的 k 个数,得出要对该数组进行排序
-
排序算法该如何选择呢?
-
根据题目要求,不要求输出的这 k 个数的顺序,考虑使用快速排序
-
因为是输出最小的 k 个数,索引从 0 开始,所以当基准数为 k+1 小的数时,这个基准数的左边子数组就是我们要找的 k 个数,也就是基准数索引为 k 时
-
使用快速排序划分子数组,每划分一次看基准数索引是否等于 k
-
若 k < 基准数索引 ,代表第 k+1 小的数字在 左子数组 中,则递归左子数组
-
若 k > 基准数索引 ,代表第 k+1 小的数字在 右子数组 中,则递归右子数组
-
否则直接返回数组前 k 个数字
题解:
class Solution {public int[] getLeastNumbers(int[] arr, int k) {if (k >= arr.length) return arr;return quickSort(arr, k, 0, arr.length-1);}private int[] quickSort(int[] arr, int k, int l, int r){int i = l, j = r;while (i<j){while (i<j && arr[j] >= arr[l]) j--;while (i<j && arr[i] <= arr[l]) i++;swap(arr,i,j);}swap(arr,i,l);//基准数索引 > k,递归左子数组if (i > k) return quickSort(arr, k, l, i-1);//基准数索引 < k,递归右子数组if (i < k) return quickSort(arr, k, i+1, r);return Arrays.copyOf(arr, k);}//交换方法private void swap(int[] arr, int i, int j) {int tmp = arr[i];arr[i] = arr[j];arr[j] = tmp;}
}
相关文章:
【剑指 Offer 40】最小的k个数
题目: 输入整数数组 arr ,找出其中最小的 k 个数。例如,输入 4、5、1、6、2、7、3、8 这 8 个数字,则最小的 4 个数字是 1、2、3、4。 示例: 输入:arr [3,2,1], k 2 输出:[1,2] 或者 [2,1] …...
vue3+vite在main.ts文件中引入./App.vue报错(./App.vue不是模块)
问题 如下图: 方法一 下载TypeScript Vue Plugin (Volar)插件就不报红了,看它的描述应该就是ts文件可以识别vue文件。 方法二 在src文件夹下添加env.d.ts文件,添加以下代码: declare module *.vue {import type { DefineC…...
【LeetCode】102. 二叉树的层序遍历、107. 二叉树的层序遍历 II
作者:小卢 专栏:《Leetcode》 喜欢的话:世间因为少年的挺身而出,而更加瑰丽。 ——《人民日报》 102. 二叉树的层序遍历 102. 二叉树的层序遍历 给你二叉树的根节点 root ,返回其节…...
HTML详解连载(2)
HTML详解连载(2) 专栏链接 [link](http://t.csdn.cn/xF0H3)下面进行专栏介绍 开始喽超链接作用代码示例解释经验分享 音频标签代码示例注意强调 视频标签代码示例注意强调 列表作用:布局内容排列整齐的区域。分类:无序列表&#x…...
qt事件系统源码-----定时器
qt定时器的使用一般有以下几种方式: 1、直接使用QTimer对象,绑定定时器的timeout信号; 2、使用QTimer的静态方法singleshot方法,产生一个一次性的定时事件 3、在QObject子类中,调用startTimer方法,产生定…...
【Android】ViewBinding+DataBinding+MVVM新手快速上手
为什么写这篇博客 网上大部分博客,代码量都比较大,把实际的业务都代入进去了 这篇博客的目的,就是为了讲解基本原理和使用思路,然后给出一个最简单的Demo 这里不讲解具体用法,那样篇幅会太长,直接看Demo…...
生成式人工智能模型:提升营销分析用户体验
使用生成式人工智能来改善分析体验,使业务用户能够询问有关我们数据平台中可用数据的任何信息。 在本文中,我们将解释如何使用新的生成式人工智能模型 ( LLM ) 来改善业务用户在我们的分析平台上的体验。假设我们为零售销售经理提供 Web 应用程序或移动应…...
【并发编程】无锁环形队列Disruptor并发框架使用
Disruptor 是苹国外厂本易公司LMAX开发的一个高件能列,研发的初夷是解决内存队列的延识问顾在性能测试中发现竟然与10操作处于同样的数量级),基于Disruptor开发的系统单线程能支撑每秒600万订单,2010年在QCn演讲后,获得了业界关注…...
【C语言】初阶指针详解
大家好,我是苏貝,本篇博客带大家了解C语言中令人头疼的指针,如果大家觉得我写的不错的话,可以给我一个赞👍吗,感谢❤️ 使用的是VS2019编译器,默认为32位平台 文章目录 ①指针是什么②指针定义与…...
ElasticSearch:项目实战(1)
es环境搭建参考:ElasticSearch:环境搭建步骤_Success___的博客-CSDN博客 需求: 用户输入关键可搜索文章列表 关键词高亮显示 文章列表展示与home展示一样,当用户点击某一篇文章,可查看文章详情 思路: …...
React 实现文件分片上传和下载
React 实现文件分片上传和下载 在开发中,文件的上传和下载是常见的需求。然而,当面对大型文件时,直接的上传和下载方式可能会遇到一些问题,比如网络传输不稳定、文件过大导致传输时间过长等等。为了解决这些问题,我们…...
2023.8.13
atcoder_abc\AtCoder Beginner Contest 310\E_NAND_repeatedly //题意:给定一个n长度的01串,计算f(l,r)(l<r,l在1~n,r在1~n)的和,f的计算(ai,a(i1))运算,有0就为1,11为0 //若f(l,r)1,则f(l,r-1)为0或sr为0,即只取决于上一位的情况和当前位ÿ…...
kvm not all arguments converted during string
kylin virt-manager 远程镜像制作问题记录(not all arguments ) 项目场景: 服务器端安装的OS版本:Kylin-Server-10-SP1-Release-Build20-20210518-arm64-2021-05-18 客户端安装的OS版本:Kylin-Server-10-SP1-Release-Build20-20210518-x86_…...
JVM 基础
巩固基础,砥砺前行 。 只有不断重复,才能做到超越自己。 能坚持把简单的事情做到极致,也是不容易的。 JVM 类加载机制 JVM 类加载机制分为五个部分:加载,验证,准备,解析,初始化&am…...
智谷星图赵俊:让人才和区块链产业“双向奔赴”丨对话MVP
区块链产业需要什么样的人才?赵俊很有发言权。 赵俊是北京智谷星图科技有限公司的技术总监,也是FISCO BCOS官方认证讲师。他2017年接触区块链,随后选择人才培育领域深耕。“为区块链行业引进更多人才这件事很有价值,跟我的职业理…...
C# Equals()方法报错:NullReferenceException was unhandled
下面是一个C# Equals()方法的例子,执行时报错了 static void Main(string[] args) {string name "sandeep";string myName null;Console.WriteLine(" operator result is {0}", name myName);Console.WriteLine("Equals method result…...
Linux下C语言调用libcurl库获取天气预报信息
一、概述 当前文章介绍如何在Linux(Ubuntu)下使用C语言调用libcurl库获取天气预报的方法。通过HTTP GET请求访问百度天气API,并解析返回的JSON数据,可以获取指定城市未来7天的天气预报信息。 二、设计思路 【1】使用libcurl库进…...
“深入解析JVM:Java虚拟机原理和内部结构“
标题:深入解析JVM:Java虚拟机原理和内部结构 摘要:本文将深入解析JVM(Java虚拟机)的原理和内部结构。我们将从JVM的基础概念开始,逐步介绍其组成部分,包括类加载器、运行时数据区、字节码解释器…...
Arrays.asList() 返回的list不能add,remove
一.Arrays.asList() 返回的list不能add,remove Arrays.asList()返回的是List,而且是一个定长的List,所以不能转换为ArrayList,只能转换为AbstractList 原因在于asList()方法返回的是某个数组的列表形式,返回的列表只是数组的另一个视图,而数组本身并没…...
命令执行漏洞
1、命令执行漏洞 1.1、简介 Django是用Python开发的一个免费开源的Web结构,几乎包括了Web使用方方面面,能够用于快速建立高性能、文雅的网站,Diango提供了许多网站后台开发常常用到的模块,使开发者可以专注于业务部分。 1.2、漏…...
linux之kylin系统nginx的安装
一、nginx的作用 1.可做高性能的web服务器 直接处理静态资源(HTML/CSS/图片等),响应速度远超传统服务器类似apache支持高并发连接 2.反向代理服务器 隐藏后端服务器IP地址,提高安全性 3.负载均衡服务器 支持多种策略分发流量…...
HBuilderX安装(uni-app和小程序开发)
下载HBuilderX 访问官方网站:https://www.dcloud.io/hbuilderx.html 根据您的操作系统选择合适版本: Windows版(推荐下载标准版) Windows系统安装步骤 运行安装程序: 双击下载的.exe安装文件 如果出现安全提示&…...
Pinocchio 库详解及其在足式机器人上的应用
Pinocchio 库详解及其在足式机器人上的应用 Pinocchio (Pinocchio is not only a nose) 是一个开源的 C 库,专门用于快速计算机器人模型的正向运动学、逆向运动学、雅可比矩阵、动力学和动力学导数。它主要关注效率和准确性,并提供了一个通用的框架&…...
【LeetCode】算法详解#6 ---除自身以外数组的乘积
1.题目介绍 给定一个整数数组 nums,返回 数组 answer ,其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请 不要使用除法,且在 O…...
从实验室到产业:IndexTTS 在六大核心场景的落地实践
一、内容创作:重构数字内容生产范式 在短视频创作领域,IndexTTS 的语音克隆技术彻底改变了配音流程。B 站 UP 主通过 5 秒参考音频即可克隆出郭老师音色,生成的 “各位吴彦祖们大家好” 语音相似度达 97%,单条视频播放量突破百万…...
Canal环境搭建并实现和ES数据同步
作者:田超凡 日期:2025年6月7日 Canal安装,启动端口11111、8082: 安装canal-deployer服务端: https://github.com/alibaba/canal/releases/1.1.7/canal.deployer-1.1.7.tar.gz cd /opt/homebrew/etc mkdir canal…...
【记录坑点问题】IDEA运行:maven-resources-production:XX: OOM: Java heap space
问题:IDEA出现maven-resources-production:operation-service: java.lang.OutOfMemoryError: Java heap space 解决方案:将编译的堆内存增加一点 位置:设置setting-》构建菜单build-》编译器Complier...
spring boot使用HttpServletResponse实现sse后端流式输出消息
1.以前只是看过SSE的相关文章,没有具体实践,这次接入AI大模型使用到了流式输出,涉及到给前端流式返回,所以记录一下。 2.resp要设置为text/event-stream resp.setContentType("text/event-stream"); resp.setCharacter…...
【Zephyr 系列 16】构建 BLE + LoRa 协同通信系统:网关转发与混合调度实战
🧠关键词:Zephyr、BLE、LoRa、混合通信、事件驱动、网关中继、低功耗调度 📌面向读者:希望将 BLE 和 LoRa 结合应用于资产追踪、环境监测、远程数据采集等场景的开发者 📊篇幅预计:5300+ 字 🧭 背景与需求 在许多 IoT 项目中,单一通信方式往往难以兼顾近场数据采集…...
HTML版英语学习系统
HTML版英语学习系统 这是一个完全免费、无需安装、功能完整的英语学习工具,使用HTML CSS JavaScript实现。 功能 文本朗读练习 - 输入英文文章,系统朗读帮助练习听力和发音,适合跟读练习,模仿学习;实时词典查询 - 双…...
