【剑指 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、漏…...
vscode里如何用git
打开vs终端执行如下: 1 初始化 Git 仓库(如果尚未初始化) git init 2 添加文件到 Git 仓库 git add . 3 使用 git commit 命令来提交你的更改。确保在提交时加上一个有用的消息。 git commit -m "备注信息" 4 …...
什么是库存周转?如何用进销存系统提高库存周转率?
你可能听说过这样一句话: “利润不是赚出来的,是管出来的。” 尤其是在制造业、批发零售、电商这类“货堆成山”的行业,很多企业看着销售不错,账上却没钱、利润也不见了,一翻库存才发现: 一堆卖不动的旧货…...
Cloudflare 从 Nginx 到 Pingora:性能、效率与安全的全面升级
在互联网的快速发展中,高性能、高效率和高安全性的网络服务成为了各大互联网基础设施提供商的核心追求。Cloudflare 作为全球领先的互联网安全和基础设施公司,近期做出了一个重大技术决策:弃用长期使用的 Nginx,转而采用其内部开发…...
鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个生活电费的缴纳和查询小程序
一、项目初始化与配置 1. 创建项目 ohpm init harmony/utility-payment-app 2. 配置权限 // module.json5 {"requestPermissions": [{"name": "ohos.permission.INTERNET"},{"name": "ohos.permission.GET_NETWORK_INFO"…...
自然语言处理——Transformer
自然语言处理——Transformer 自注意力机制多头注意力机制Transformer 虽然循环神经网络可以对具有序列特性的数据非常有效,它能挖掘数据中的时序信息以及语义信息,但是它有一个很大的缺陷——很难并行化。 我们可以考虑用CNN来替代RNN,但是…...
是否存在路径(FIFOBB算法)
题目描述 一个具有 n 个顶点e条边的无向图,该图顶点的编号依次为0到n-1且不存在顶点与自身相连的边。请使用FIFOBB算法编写程序,确定是否存在从顶点 source到顶点 destination的路径。 输入 第一行两个整数,分别表示n 和 e 的值(1…...
MFC 抛体运动模拟:常见问题解决与界面美化
在 MFC 中开发抛体运动模拟程序时,我们常遇到 轨迹残留、无效刷新、视觉单调、物理逻辑瑕疵 等问题。本文将针对这些痛点,详细解析原因并提供解决方案,同时兼顾界面美化,让模拟效果更专业、更高效。 问题一:历史轨迹与小球残影残留 现象 小球运动后,历史位置的 “残影”…...
NPOI Excel用OLE对象的形式插入文件附件以及插入图片
static void Main(string[] args) {XlsWithObjData();Console.WriteLine("输出完成"); }static void XlsWithObjData() {// 创建工作簿和单元格,只有HSSFWorkbook,XSSFWorkbook不可以HSSFWorkbook workbook new HSSFWorkbook();HSSFSheet sheet (HSSFSheet)workboo…...
实战设计模式之模板方法模式
概述 模板方法模式定义了一个操作中的算法骨架,并将某些步骤延迟到子类中实现。模板方法使得子类可以在不改变算法结构的前提下,重新定义算法中的某些步骤。简单来说,就是在一个方法中定义了要执行的步骤顺序或算法框架,但允许子类…...
《信号与系统》第 6 章 信号与系统的时域和频域特性
目录 6.0 引言 6.1 傅里叶变换的模和相位表示 6.2 线性时不变系统频率响应的模和相位表示 6.2.1 线性与非线性相位 6.2.2 群时延 6.2.3 对数模和相位图 6.3 理想频率选择性滤波器的时域特性 6.4 非理想滤波器的时域和频域特性讨论 6.5 一阶与二阶连续时间系统 6.5.1 …...
