面试题 17.14.最小K个数
题目:如下图
答案:如下图
/*** Note: The returned array must be malloced, assume caller calls free().*/
void AdjustDown(int* a,int n,int root)
{int parent = root;int child = parent * 2 + 1;//默认左孩子是大的,将其与右孩子比较,如果小于右节点则换while (child<n){//变号找小的if (child + 1 < n && a[child] < a[child + 1]){ ++child;}//parent永远不可能为负数,c语言是取整运算(-1)/2=0,// 此时parent=child=0,其a[child]=a[parnet],执行breakif (a[parent] < a[child]){//交换int tmp = a[parent];a[parent] = a[child];a[child] = tmp;//向下进行迭代parent = child;child = parent * 2 + 1;}else{break;}}
}//TopK问题,先建大堆,比较,返回
int* smallestK(int* arr, int arrSize, int k, int* returnSize) {//判空*returnSize = k;//开辟返回数组指针int* retArr =(int*)malloc(sizeof(int) * k);if (k==0){return retArr;}//将arr中的元素复制到retArr中for (int i = 0; i < k; ++i){retArr[i] = arr[i];}//向下调整retArr为大堆,并且大堆中的元素个数为k个,第一次见for (int i = (k-1-1)/2 ; i>=0; --i){//字面意思就行//向下调整一调整就是“垂直”的整个路径AdjustDown(retArr, k, i);}//比较并且重新赋值?for (int j = k; j < arrSize; ++j){if (retArr[0] > arr[j]){retArr[0] = arr[j];AdjustDown(retArr, k, j);}}return retArr;
}
解析:
(1)判空k并且开辟返回数组指针
将k值赋给返回大小指针
题目中要求返回数组指针必须是malloc出来的,这里我们采用malloc函数进行开辟
判空如果k==0,那么我们返回NULL或者retArr(是空指针)都可以
*returnSize = k;
int* retArr =(int*)malloc(sizeof(int) * k);
if (k==0)
{
return retArr;
}
(2)将arr中的元素拷贝到retArr中
这里利用for循环将有k个值arr数组进行拷贝
for (int i = 0; i < k; ++i)
{
retArr[i] = arr[i];
}
(3)向下调整retArr为大堆,并且大堆中的元素个数为k个
这里我们采用建大堆而不是小堆是因为:
若采用小堆构建如下图:
第一行是数组,其中k=6,前六个构建一个小堆,如图可知当最小的值1作为堆顶时,最小的k个数的值2比1大无法进入堆中,进而使用小堆进行构建无法进行选出前6个小的元素,故我们采用大堆
采用大堆构建如下图:
显而易见元素作为最小的k个数中的2比堆顶11小那么可以入堆直接覆盖11,调整堆,使用AdjustDown()函数调整数组保持大堆的性质,使其成为大堆
for (int i = (k-1-1)/2 ; i>=0; --i)
{
//AdjustDown()字面意思就行
//向下调整一调整就是“侧方垂直”的整个路径
//由于数组的顺序是混乱的没有进行调整,无法保证AdjustDown()函数两侧都是大堆,那么我们在(k-1-1)/2的位置进行调整。k-1的意思是数组末尾的元素,其作为child结点求其parent结点为(k-1-1)/2,
AdjustDown(retArr, k, i);
}
(4)AdjustDown()函数的实现
void AdjustDown(int* a,int n,int root)
{
int parent = root;
int child = parent * 2 + 1;
while (child<n)
{
//默认左孩子是大的,将其与右孩子比较,如果小于右节点则换
这里注意当最后一个结点恰好为左节点会存在没有右孩子的情况,这里我们采用child+1<n进行判断
if (child + 1 < n && a[child] < a[child + 1])
{
++child;
}
//parent永远不可能为负数,c语言是取整运算(-1)/2=0,
// 此时parent=child=0,其a[child]=a[parnet],执行break直接跳出循环,故while循环的条件 //为child<n
if (a[parent] < a[child])
{
//交换
int tmp = a[parent];
a[parent] = a[child];
a[child] = tmp;
//向下进行迭代
//这里即字面意思AdjustDown向下调整,那么就将child的值赋给parent,重新由父结点计 //算出孩子结点,进而达到向下调整迭代的目的
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
(5)比较并且重新赋值然后调整数组成为大堆
令j=k,k为大堆的元素个数同时也为余下数组的第一个数的下标,使j<arrsize进行循环逐渐使最小的k个数进入大堆中去
如果大堆顶retArr[0]大于数组arr[j]那么则直接将arr[j]赋值给retArr[0]中,由于是大堆,那么最小的k个数是一定小于由k个数组成在大堆顶的数,那么其能够进入由k个数组成的大堆(当最小的k个数全部进入大堆中后再也没有数可以进入大堆,因为大堆上的堆顶的数是第k个最小的数,第k+1个小的数>第k个小的数,无法进入大堆),调整数组使其成为大堆
for (int j = k; j < arrSize; ++j)
{
if (retArr[0] > arr[j])
{
retArr[0] = arr[j];
//AdjustDown()函数由于堆顶两侧都是大堆故是在堆顶进行直接调整
AdjustDown(retArr, k, j);
}
}
(6)返回保存有最小的k个数的retArr数组
return retArr;
到这里我们解题完毕
如果对您有帮助的话点一个免费的赞和收藏叭!
由于作者水平不足,如果有任何错误,麻烦读者评论在评论区指点一下,谢谢!
相关文章:

面试题 17.14.最小K个数
题目:如下图 答案:如下图 /*** Note: The returned array must be malloced, assume caller calls free().*/ void AdjustDown(int* a,int n,int root) {int parent root;int child parent * 2 1;//默认左孩子是大的,将其与右孩子比较&am…...

C++实现LRU缓存(新手入门详解)
LRU的概念 LRU(Least Recently Used,最近最少使用)是一种常用的缓存淘汰策略,主要目的是在缓存空间有限的情况下,优先淘汰那些最长时间没有被访问的数据项。LRU 策略的核心思想是: 缓存空间有限࿱…...

汇昌联信数字做拼多多运营实力好吗?
汇昌联信数字在拼多多运营方面的实力如何?汇昌联信数字作为一家专注于电子商务运营服务的公司,其在拼多多平台的运营能力是值得关注的。根据市场反馈和客户评价,汇昌联信数字在拼多多的运营实力表现良好,能够为客户提供专业的店铺管理、产品…...

【云原生】Prometheus 服务自动发现使用详解
目录 一、前言 二、Prometheus常规服务监控使用现状 2.1 Prometheus监控架构图 2.2 Prometheus服务自动发现的解决方案 三、Prometheus服务自动发现介绍 3.1 什么是Prometheus服务自动发现 3.2 Prometheus自动服务发现策略 3.3 Prometheus自动服务发现应用…...

(十九)原生js案例之h5地里位置信息与高德地图的初使用
h5 地里位置信息 1. 获取当前位置信息 window.onload function () {const oBtn document.querySelector("#btn");const oBox document.querySelector("#box");oBtn.onclick function () {window.navigator.geolocation.getCurrentPosition(function (…...

三、基础语法2(30小时精通C++和外挂实战)
三、基础语法2(30小时精通C和外挂实战) B-02内联函数B-04内联函数与宏B-05_constB-06引用B-07引用的本质B-08-汇编1-X86-X64汇编B-09-汇编2-内联汇编B-10-汇编3-MOV指令C-02-汇编5-其他常见指令C-05-汇编8-反汇编分析C-07-const引用、特点 B-02内联函数 …...

gitee设置ssh公钥密码频繁密码验证
gitee中可以创建私有项目,但是在clone或者push都需要输入密码, 比较繁琐。 公钥则可以解决该问题,将私钥放在本地,公钥放在gitee上,当对项目进行操作时带有的私钥会在gitee和公钥进行验证,避免了手动输入密…...

BGP选路之Next Hop
原理概述 当一台BGP路由器中存在多条去往同一目标网络的BGP路由时,BGP协议会对这些BGP路由的属性进行比较,以确定出去往该目标网络的最优BGP路由,然后将该最优BGP路由与去往同一目标网络的其他协议路由进行比较,从而决定是否将该最优BGP路由放进P路由表中…...
牛客14666(优先屏障) + 牛客14847(Masha与老鼠)
文章目录 写在前面14666-优先屏障思路编程 14847-Masha与老鼠思路编程 写在前面 昨天刷的这两道题写了很久,特别是Masha与老鼠这道题,写了都快3个小时,主要还是理解代码逻辑有点难,不过写完之后感觉收获挺大的,给我以…...

Git下载与安装
下载网址:https://git-scm.com/downloads 下载之后开始安装 选择安装路径,next 选择需要安装的组件,这里默认即可,next 选择菜单文件夹,这里默认即可,next 选择默认编辑器,默认推荐的即可&…...
创建vue2/vue3项目
目录 创建一个Vue2项目创建一个Vue3项目 创建一个Vue2项目 ## 安装Vue-Cli : npm install -g vue/cli // Vue CLI 4.x 需要 Node.js v8.9 或更高版本 (推荐 v10 以上)vue --version // 检测版本是否正确## 创建一个项目: vue create hello-world // hel…...
IOS七层模型对应的网络协议和物理设备
以下是网络模型、对应的协议以及对应的物理设备的表格总结: 网络模型层次主要功能对应协议对应物理设备物理层透明的传输比特流,确定机械及电气规范RS-232、V.35、RJ-45、FDDI等中继器、集线器、网线、调制解调器、网卡数据链路层将比特组装成帧和点到点…...

论文复现:Predictive Control of Networked Multiagent Systems via Cloud Computing
Predictive Control of Networked Multiagent Systems via Cloud Computing论文复现 文章目录 Predictive Control of Networked Multiagent Systems via Cloud Computing论文复现论文摘要系统参数初始化系统模型观测器预测过程控制器设计系统的整体框图仿真结果 论文摘要 翻译…...

JSON 文件存储
JSON 全称为: JavaScript Object Notation 也就是 javaScript 对象标记,通过对象和数组的组合来表示数据, 虽然构造简洁,但是结构化程度非常高, 是一种轻量级的数据交换格式 对象和数组 在 JavaScript 语言中&#…...
python——pynput
pynput 是一个 Python 库,用于控制和监听键盘与鼠标输入。它在 Windows、macOS 和 Linux 上都可以工作,为用户提供了一个跨平台的输入事件处理方式。pynput 包含两个主要模块:keyboard 和 mouse,分别用于处理键盘和鼠标事件。 主…...

[用AI日进斗金系列]用码上飞在企微接单开发一个项目管理系统!
今天是【日进斗金】系列的第二期文章。 先给不了解这个系列的朋友们介绍一下,在这个系列的文章中,我们将会在企微的工作台的“需求发布页面”中寻找有软件开发需求的用户 并通过自研的L4级自动化智能软件开发平台「码上飞CodeFlying」让AI生成应用以解…...

《JavaEE篇》--多线程(2)
《JavaEE篇》--多线程(1) 线程安全 线程不安全 我们先来观察一个线程不安全的案例: public class Demo {private static int count 0;public static void main(String[] args) throws InterruptedException {Thread t1 new Thread(() -> {//让count自增5W次…...

防爆智能手机如何助力电气行业保驾护航?
在电气行业的智能化转型浪潮中,防爆智能手机以其强大的数据处理能力、实时通讯功能及高度集成的安全特性,正成为保障电力网络稳定运行、预防安全隐患的得力助手。 防爆智能手机在电气行业中发挥着重要的保驾护航作用,主要体现在以下几个方面&…...
24.7.24数组|那几个课后得做的题
1、对长整形数据进行反转 2、对字符串进行反转 一、题目地址: 1. 实现一个函数atoi,使其能够将字符串转换整数 (Leetcode 8/中等). - 力扣(LeetCode) 2. 颠倒给定的32位无符号整数的二进制位(Leetcode 190/简单&…...
03Spring底层架构核心概念解析
为了感谢罕哥对我工作的帮助,特此记录下学习过程,期待成为和罕哥一样优秀的人 时间:2024.7.13 内容:spring源码课程3学习记录 一、BeanDefinition BeanDefinition表示Bean的定义,BeanDefinition中存在很多属性用来…...

装饰模式(Decorator Pattern)重构java邮件发奖系统实战
前言 现在我们有个如下的需求,设计一个邮件发奖的小系统, 需求 1.数据验证 → 2. 敏感信息加密 → 3. 日志记录 → 4. 实际发送邮件 装饰器模式(Decorator Pattern)允许向一个现有的对象添加新的功能,同时又不改变其…...
Cursor实现用excel数据填充word模版的方法
cursor主页:https://www.cursor.com/ 任务目标:把excel格式的数据里的单元格,按照某一个固定模版填充到word中 文章目录 注意事项逐步生成程序1. 确定格式2. 调试程序 注意事项 直接给一个excel文件和最终呈现的word文件的示例,…...
基于大模型的 UI 自动化系统
基于大模型的 UI 自动化系统 下面是一个完整的 Python 系统,利用大模型实现智能 UI 自动化,结合计算机视觉和自然语言处理技术,实现"看屏操作"的能力。 系统架构设计 #mermaid-svg-2gn2GRvh5WCP2ktF {font-family:"trebuchet ms",verdana,arial,sans-…...
应用升级/灾备测试时使用guarantee 闪回点迅速回退
1.场景 应用要升级,当升级失败时,数据库回退到升级前. 要测试系统,测试完成后,数据库要回退到测试前。 相对于RMAN恢复需要很长时间, 数据库闪回只需要几分钟。 2.技术实现 数据库设置 2个db_recovery参数 创建guarantee闪回点,不需要开启数据库闪回。…...
Go 语言接口详解
Go 语言接口详解 核心概念 接口定义 在 Go 语言中,接口是一种抽象类型,它定义了一组方法的集合: // 定义接口 type Shape interface {Area() float64Perimeter() float64 } 接口实现 Go 接口的实现是隐式的: // 矩形结构体…...
macOS多出来了:Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用
文章目录 问题现象问题原因解决办法 问题现象 macOS启动台(Launchpad)多出来了:Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用。 问题原因 很明显,都是Google家的办公全家桶。这些应用并不是通过独立安装的…...
ffmpeg(四):滤镜命令
FFmpeg 的滤镜命令是用于音视频处理中的强大工具,可以完成剪裁、缩放、加水印、调色、合成、旋转、模糊、叠加字幕等复杂的操作。其核心语法格式一般如下: ffmpeg -i input.mp4 -vf "滤镜参数" output.mp4或者带音频滤镜: ffmpeg…...
VTK如何让部分单位不可见
最近遇到一个需求,需要让一个vtkDataSet中的部分单元不可见,查阅了一些资料大概有以下几种方式 1.通过颜色映射表来进行,是最正规的做法 vtkNew<vtkLookupTable> lut; //值为0不显示,主要是最后一个参数,透明度…...
JDK 17 新特性
#JDK 17 新特性 /**************** 文本块 *****************/ python/scala中早就支持,不稀奇 String json “”" { “name”: “Java”, “version”: 17 } “”"; /**************** Switch 语句 -> 表达式 *****************/ 挺好的ÿ…...
汇编常见指令
汇编常见指令 一、数据传送指令 指令功能示例说明MOV数据传送MOV EAX, 10将立即数 10 送入 EAXMOV [EBX], EAX将 EAX 值存入 EBX 指向的内存LEA加载有效地址LEA EAX, [EBX4]将 EBX4 的地址存入 EAX(不访问内存)XCHG交换数据XCHG EAX, EBX交换 EAX 和 EB…...