【剑指 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、漏…...
【JavaEE】-- HTTP
1. HTTP是什么? HTTP(全称为"超文本传输协议")是一种应用非常广泛的应用层协议,HTTP是基于TCP协议的一种应用层协议。 应用层协议:是计算机网络协议栈中最高层的协议,它定义了运行在不同主机上…...
基础测试工具使用经验
背景 vtune,perf, nsight system等基础测试工具,都是用过的,但是没有记录,都逐渐忘了。所以写这篇博客总结记录一下,只要以后发现新的用法,就记得来编辑补充一下 perf 比较基础的用法: 先改这…...
在Ubuntu中设置开机自动运行(sudo)指令的指南
在Ubuntu系统中,有时需要在系统启动时自动执行某些命令,特别是需要 sudo权限的指令。为了实现这一功能,可以使用多种方法,包括编写Systemd服务、配置 rc.local文件或使用 cron任务计划。本文将详细介绍这些方法,并提供…...
python如何将word的doc另存为docx
将 DOCX 文件另存为 DOCX 格式(Python 实现) 在 Python 中,你可以使用 python-docx 库来操作 Word 文档。不过需要注意的是,.doc 是旧的 Word 格式,而 .docx 是新的基于 XML 的格式。python-docx 只能处理 .docx 格式…...
Spring Boot面试题精选汇总
🤟致敬读者 🟩感谢阅读🟦笑口常开🟪生日快乐⬛早点睡觉 📘博主相关 🟧博主信息🟨博客首页🟫专栏推荐🟥活动信息 文章目录 Spring Boot面试题精选汇总⚙️ **一、核心概…...
2023赣州旅游投资集团
单选题 1.“不登高山,不知天之高也;不临深溪,不知地之厚也。”这句话说明_____。 A、人的意识具有创造性 B、人的认识是独立于实践之外的 C、实践在认识过程中具有决定作用 D、人的一切知识都是从直接经验中获得的 参考答案: C 本题解…...
云原生玩法三问:构建自定义开发环境
云原生玩法三问:构建自定义开发环境 引言 临时运维一个古董项目,无文档,无环境,无交接人,俗称三无。 运行设备的环境老,本地环境版本高,ssh不过去。正好最近对 腾讯出品的云原生 cnb 感兴趣&…...
html css js网页制作成品——HTML+CSS榴莲商城网页设计(4页)附源码
目录 一、👨🎓网站题目 二、✍️网站描述 三、📚网站介绍 四、🌐网站效果 五、🪓 代码实现 🧱HTML 六、🥇 如何让学习不再盲目 七、🎁更多干货 一、👨…...
短视频矩阵系统文案创作功能开发实践,定制化开发
在短视频行业迅猛发展的当下,企业和个人创作者为了扩大影响力、提升传播效果,纷纷采用短视频矩阵运营策略,同时管理多个平台、多个账号的内容发布。然而,频繁的文案创作需求让运营者疲于应对,如何高效产出高质量文案成…...
Qt 事件处理中 return 的深入解析
Qt 事件处理中 return 的深入解析 在 Qt 事件处理中,return 语句的使用是另一个关键概念,它与 event->accept()/event->ignore() 密切相关但作用不同。让我们详细分析一下它们之间的关系和工作原理。 核心区别:不同层级的事件处理 方…...
