当前位置: 首页 > news >正文

面试题 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个数

题目&#xff1a;如下图 答案&#xff1a;如下图 /*** 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;//默认左孩子是大的&#xff0c;将其与右孩子比较&am…...

C++实现LRU缓存(新手入门详解)

LRU的概念 LRU&#xff08;Least Recently Used&#xff0c;最近最少使用&#xff09;是一种常用的缓存淘汰策略&#xff0c;主要目的是在缓存空间有限的情况下&#xff0c;优先淘汰那些最长时间没有被访问的数据项。LRU 策略的核心思想是&#xff1a; 缓存空间有限&#xff1…...

汇昌联信数字做拼多多运营实力好吗?

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

【云原生】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&#xff08;30小时精通C和外挂实战&#xff09; 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中可以创建私有项目&#xff0c;但是在clone或者push都需要输入密码&#xff0c; 比较繁琐。 公钥则可以解决该问题&#xff0c;将私钥放在本地&#xff0c;公钥放在gitee上&#xff0c;当对项目进行操作时带有的私钥会在gitee和公钥进行验证&#xff0c;避免了手动输入密…...

BGP选路之Next Hop

原理概述 当一台BGP路由器中存在多条去往同一目标网络的BGP路由时&#xff0c;BGP协议会对这些BGP路由的属性进行比较,以确定出去往该目标网络的最优BGP路由,然后将该最优BGP路由与去往同一目标网络的其他协议路由进行比较&#xff0c;从而决定是否将该最优BGP路由放进P路由表中…...

牛客14666(优先屏障) + 牛客14847(Masha与老鼠)

文章目录 写在前面14666-优先屏障思路编程 14847-Masha与老鼠思路编程 写在前面 昨天刷的这两道题写了很久&#xff0c;特别是Masha与老鼠这道题&#xff0c;写了都快3个小时&#xff0c;主要还是理解代码逻辑有点难&#xff0c;不过写完之后感觉收获挺大的&#xff0c;给我以…...

Git下载与安装

下载网址&#xff1a;https://git-scm.com/downloads 下载之后开始安装 选择安装路径&#xff0c;next 选择需要安装的组件&#xff0c;这里默认即可&#xff0c;next 选择菜单文件夹&#xff0c;这里默认即可&#xff0c;next 选择默认编辑器&#xff0c;默认推荐的即可&…...

创建vue2/vue3项目

目录 创建一个Vue2项目创建一个Vue3项目 创建一个Vue2项目 ## 安装Vue-Cli &#xff1a; npm install -g vue/cli // Vue CLI 4.x 需要 Node.js v8.9 或更高版本 (推荐 v10 以上)vue --version // 检测版本是否正确## 创建一个项目&#xff1a; vue create hello-world // hel…...

IOS七层模型对应的网络协议和物理设备

以下是网络模型、对应的协议以及对应的物理设备的表格总结&#xff1a; 网络模型层次主要功能对应协议对应物理设备物理层透明的传输比特流&#xff0c;确定机械及电气规范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 全称为&#xff1a; JavaScript Object Notation 也就是 javaScript 对象标记&#xff0c;通过对象和数组的组合来表示数据&#xff0c; 虽然构造简洁&#xff0c;但是结构化程度非常高&#xff0c; 是一种轻量级的数据交换格式 对象和数组 在 JavaScript 语言中&#…...

python——pynput

pynput 是一个 Python 库&#xff0c;用于控制和监听键盘与鼠标输入。它在 Windows、macOS 和 Linux 上都可以工作&#xff0c;为用户提供了一个跨平台的输入事件处理方式。pynput 包含两个主要模块&#xff1a;keyboard 和 mouse&#xff0c;分别用于处理键盘和鼠标事件。 主…...

[用AI日进斗金系列]用码上飞在企微接单开发一个项目管理系统!

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

《JavaEE篇》--多线程(2)

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

防爆智能手机如何助力电气行业保驾护航?

在电气行业的智能化转型浪潮中&#xff0c;防爆智能手机以其强大的数据处理能力、实时通讯功能及高度集成的安全特性&#xff0c;正成为保障电力网络稳定运行、预防安全隐患的得力助手。 防爆智能手机在电气行业中发挥着重要的保驾护航作用&#xff0c;主要体现在以下几个方面&…...

24.7.24数组|那几个课后得做的题

1、对长整形数据进行反转 2、对字符串进行反转 一、题目地址&#xff1a; 1. 实现一个函数atoi&#xff0c;使其能够将字符串转换整数 (Leetcode 8/中等). - 力扣&#xff08;LeetCode&#xff09; 2. 颠倒给定的32位无符号整数的二进制位&#xff08;Leetcode 190/简单&…...

03Spring底层架构核心概念解析

为了感谢罕哥对我工作的帮助&#xff0c;特此记录下学习过程&#xff0c;期待成为和罕哥一样优秀的人 时间&#xff1a;2024.7.13 内容&#xff1a;spring源码课程3学习记录 一、BeanDefinition BeanDefinition表示Bean的定义&#xff0c;BeanDefinition中存在很多属性用来…...

OpenLayers 可视化之热力图

注&#xff1a;当前使用的是 ol 5.3.0 版本&#xff0c;天地图使用的key请到天地图官网申请&#xff0c;并替换为自己的key 热力图&#xff08;Heatmap&#xff09;又叫热点图&#xff0c;是一种通过特殊高亮显示事物密度分布、变化趋势的数据可视化技术。采用颜色的深浅来显示…...

java 实现excel文件转pdf | 无水印 | 无限制

文章目录 目录 文章目录 前言 1.项目远程仓库配置 2.pom文件引入相关依赖 3.代码破解 二、Excel转PDF 1.代码实现 2.Aspose.License.xml 授权文件 总结 前言 java处理excel转pdf一直没找到什么好用的免费jar包工具,自己手写的难度,恐怕高级程序员花费一年的事件,也…...

抖音增长新引擎:品融电商,一站式全案代运营领跑者

抖音增长新引擎&#xff1a;品融电商&#xff0c;一站式全案代运营领跑者 在抖音这个日活超7亿的流量汪洋中&#xff0c;品牌如何破浪前行&#xff1f;自建团队成本高、效果难控&#xff1b;碎片化运营又难成合力——这正是许多企业面临的增长困局。品融电商以「抖音全案代运营…...

DIY|Mac 搭建 ESP-IDF 开发环境及编译小智 AI

前一阵子在百度 AI 开发者大会上&#xff0c;看到基于小智 AI DIY 玩具的演示&#xff0c;感觉有点意思&#xff0c;想着自己也来试试。 如果只是想烧录现成的固件&#xff0c;乐鑫官方除了提供了 Windows 版本的 Flash 下载工具 之外&#xff0c;还提供了基于网页版的 ESP LA…...

04-初识css

一、css样式引入 1.1.内部样式 <div style"width: 100px;"></div>1.2.外部样式 1.2.1.外部样式1 <style>.aa {width: 100px;} </style> <div class"aa"></div>1.2.2.外部样式2 <!-- rel内表面引入的是style样…...

【RockeMQ】第2节|RocketMQ快速实战以及核⼼概念详解(二)

升级Dledger高可用集群 一、主从架构的不足与Dledger的定位 主从架构缺陷 数据备份依赖Slave节点&#xff0c;但无自动故障转移能力&#xff0c;Master宕机后需人工切换&#xff0c;期间消息可能无法读取。Slave仅存储数据&#xff0c;无法主动升级为Master响应请求&#xff…...

Java入门学习详细版(一)

大家好&#xff0c;Java 学习是一个系统学习的过程&#xff0c;核心原则就是“理论 实践 坚持”&#xff0c;并且需循序渐进&#xff0c;不可过于着急&#xff0c;本篇文章推出的这份详细入门学习资料将带大家从零基础开始&#xff0c;逐步掌握 Java 的核心概念和编程技能。 …...

Android Bitmap治理全解析:从加载优化到泄漏防控的全生命周期管理

引言 Bitmap&#xff08;位图&#xff09;是Android应用内存占用的“头号杀手”。一张1080P&#xff08;1920x1080&#xff09;的图片以ARGB_8888格式加载时&#xff0c;内存占用高达8MB&#xff08;192010804字节&#xff09;。据统计&#xff0c;超过60%的应用OOM崩溃与Bitm…...

Java 二维码

Java 二维码 **技术&#xff1a;**谷歌 ZXing 实现 首先添加依赖 <!-- 二维码依赖 --><dependency><groupId>com.google.zxing</groupId><artifactId>core</artifactId><version>3.5.1</version></dependency><de…...

python报错No module named ‘tensorflow.keras‘

是由于不同版本的tensorflow下的keras所在的路径不同&#xff0c;结合所安装的tensorflow的目录结构修改from语句即可。 原语句&#xff1a; from tensorflow.keras.layers import Conv1D, MaxPooling1D, LSTM, Dense 修改后&#xff1a; from tensorflow.python.keras.lay…...