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

TOP K问题:利用堆排序找出数组中最小的k个数

设计一个算法,找出数组中最小的k个数。以任意顺序返回这k个数均可。

找小的数需要建大堆来解决,首先将数组中前K个数建成一个大堆,将从k+1个数直到数组结束的所有数与堆顶的数进行比较,如果比堆顶的数小,则替换堆顶的数据,然后在向下调整,重新形成一个新的大堆,如果比堆顶的数小,则不替换。以此循环,直至数组k+1个数到数组结束所有的数都比较完,最后留在堆里的数就是最小的k个数。用题中的题目来说:使用前4个数 1 3 5 7 来建一个大堆。

替换了之后由于不是一个大堆,所以进行向下调整,形成一个新的大堆。

替换了之后进行向下调整

最后输出的结果

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>

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 + 1] > a[child])//选出大的那个孩子
        {
            child++;
        }
        if (a[child] > a[parent])
        {
            int tmp = a[child];
            a[child] = a[parent];
            a[parent] = tmp;
            parent = child;
            child = parent * 2 + 1;
        }
        else
        {
            break;
        }
    }
}

int* smallestK(int* arr, int arrSize, int k, int* returnSize)
{
    *returnSize = k;
    if (k == 0)
        return NULL;
    int* retArr = (int*)malloc(sizeof(int) * k);
    int i = 0;
    for (i = 0; i < k; i++)
    {
        retArr[i] = arr[i];
    }
    //建K个数的大堆
    for (i = (k - 1 - 1) / 2; i >= 0; i--)
    {
        AdjustDown(retArr, k, i);
    }

    for (i = k; i < arrSize; i++)
    {
        if (arr[i] < retArr[0])
        {
            retArr[0] = arr[i];
            AdjustDown(retArr, k, 0);
        }
    }
    *returnSize = k;

    return retArr;
}

int main()
{
    // 测试数据
    int arr[] = { 1,3,5,7,2,4,6,8 };
    int arrSize = sizeof(arr) / sizeof(arr[0]);
    int k = 4;
    int returnSize;

    // 调用 smallestK 函数
    int* result = smallestK(arr, arrSize, k, &returnSize);

    // 输出结果
    printf("The smallest %d elements are:\n", k);
    for (int i = 0; i < returnSize; i++) {
        printf("%d ", result[i]);
    }
    printf("\n");

    // 释放分配的内存
    free(result);
    return 0;
}

相关文章:

TOP K问题:利用堆排序找出数组中最小的k个数

设计一个算法&#xff0c;找出数组中最小的k个数。以任意顺序返回这k个数均可。 找小的数需要建大堆来解决&#xff0c;首先将数组中前K个数建成一个大堆&#xff0c;将从k1个数直到数组结束的所有数与堆顶的数进行比较&#xff0c;如果比堆顶的数小&#xff0c;则替换堆顶的数…...

《信息传播:人工智能助力驱散虚假信息阴霾》

在信息爆炸的时代&#xff0c;虚假信息和谣言如同脱缰野马&#xff0c;肆意传播&#xff0c;对社会秩序和公众生活造成了严重影响。人工智能作为一种强大的技术工具&#xff0c;正逐渐成为信息传播的有力助手&#xff0c;为防止虚假信息和谣言扩散提供了新的途径。 虚假信息和…...

数据权限和角色权限区别

1、概念 角色权限&#xff08;Role-Based Access Control, RBAC&#xff09;和数据权限&#xff08;Data Access Control&#xff09;是两种不同的权限管理策略&#xff0c;它们在权限控制的侧重点和应用场景上有所区别&#xff1a; 角色权限&#xff08;RBAC&#xff…...

Flink的多流转换(分流-侧输出流、合流-union、connect、join)

在实际应用中&#xff0c;我们可能要将多个不同来源的数据连接合并在一起进行处理&#xff0c;也有可能要将一条流拆分成多条流进行处理&#xff0c;这就涉及到了Flink的多流转换问题。简单来说&#xff0c;就是分流和合流两大操作&#xff0c;分流主要通过侧输出流实现&#x…...

DirectUI属性表

<?xml version"1.0" encoding"UTF-8"?> <Controls><Window parent""><Attribute name"size" default"0,0" type"SIZE" comment"窗口的初始化大小,如(800,600)"/><Attribu…...

RBAC权限控制

1、Spring Security 是一个功能强大的Java安全框架&#xff0c;它提供了全面的安全认证和授权的支持。 2 SpringSecurity配置类&#xff08;源码逐行解析&#xff09; Spring Security的配置类是实现安全控制的核心部分 开启Spring Security各种功能&#xff0c;以确保Web应…...

STM32高级物联网通信之以太网通讯

目录 以太网通讯基础知识 什么是以太网 互联网和以太网的区别 1)概念与范围 (1)互联网 (2)以太网 2)技术特点 (1)互联网 (2)以太网 3)应用场景 (1)互联网 (2)以太网 以太网的层次 1)物理层 2)数据链路层 OSI 7层模型 TCPIP 4层模型 一些常见…...

【小程序】全局配置window和tabBar

目录 全局配置 1. 全局配置文件及常用的配置项 全局配置 - window 1. 小程序窗口的组成部分 2. 了解 window 节点常用的配置项 ​编辑 3. 设置导航栏的标题 4. 设置导航栏的背景色 5. 设置导航栏的标题颜色 6. 全局开启下拉刷新功能 7. 设置下拉刷新时窗口的背景色 …...

详解VHDL如何编写Testbench

1.概述 仿真测试平台文件(Testbench)是可以用来验证所设计的硬件模型正确性的 VHDL模型&#xff0c;它为所测试的元件提供了激励信号&#xff0c;可以以波形的方式显示仿真结果或把测试结果存储到文件中。这里所说的激励信号可以直接集成在测试平台文件中&#xff0c;也可以从…...

冥想的实践

这是我某一天的正念和冥想实践&#xff0c;我对正念练习、冥想练习进行了分别的统计。 正念练习&#xff1a;1分钟**5次 冥想&#xff1a;15分钟10分钟 正念练习&#xff0c;基本在工作休息时间练习。当然&#xff0c;工作过程中&#xff0c;也有一部分时间会有正念的状态&am…...

STM32F103RCT6学习之四:定时器

1.基础 定时器可以对输入的时钟进行计数&#xff0c;并在计数值达到设定值时触发中断 16位计数器、预分频器、自动重装寄存器的时基单元&#xff0c;在72MHz计数时钟下可以实现最大59.65s的定时 不仅具备基本的定时中断功能&#xff0c;而且还包含内外时钟源选择、输入捕获、…...

如何在网页端使用 IDE 高效地阅读 GitHub 源码?

如何在网页端使用 IDE 高效地阅读 GitHub 源码&#xff1f; 前言什么是 GitHub1s&#xff1f;使用 GitHub1s 阅读 browser-use 项目源码步骤 1: 打开 GitHub 项目页面步骤 2: 修改 URL 使用 GitHub1s步骤 3: 浏览文件结构步骤 4: 使用代码高亮和智能补全功能步骤 5: 快速跳转和…...

易基因: BS+ChIP-seq揭示DNA甲基化调控非编码RNA(VIM-AS1)抑制肿瘤侵袭性|Exp Mol Med

大家好&#xff0c;这里是专注表观组学十余年&#xff0c;领跑多组学科研服务的易基因。 肝细胞癌&#xff08;hepatocellular carcinoma&#xff0c;HCC&#xff09;早期复发仍然是一个具有挑战性的领域&#xff0c;其中涉及的机制尚未完全被理解。尽管微血管侵犯&#xff08…...

欢迪迈手机商城设计与实现基于(代码+数据库+LW)

摘 要 现代经济快节奏发展以及不断完善升级的信息化技术&#xff0c;让传统数据信息的管理升级为软件存储&#xff0c;归纳&#xff0c;集中处理数据信息的管理方式。本欢迪迈手机商城就是在这样的大环境下诞生&#xff0c;其可以帮助管理者在短时间内处理完毕庞大的数据信息…...

数据库基础与应用:从概念到实践

数据库是信息技术中的核心组件之一&#xff0c;是现代计算机系统中不可或缺的部分。无论是日常应用的社交网络、电子商务网站&#xff0c;还是企业级的大型系统&#xff0c;几乎所有的信息管理都离不开数据库。那么&#xff0c;数据库究竟是什么&#xff1f;它是如何工作的&…...

jenkins集成工具(一)部署php项目

目录 什么是CI 、CD Jenkins集成工具 一、Jenkins介绍 二、jenkins的安装和部署 环境部署 安装jenkins 安装gitlab 配置镜像源进行安装 修改密码 安装git工具 上传测试代码 Jenkins部署php项目wordpress 发布php代码 安装插件 测试代码发布 实现发布成功发送邮件…...

17_HTML5 Web 存储 --[HTML5 API 学习之旅]

HTML5 Web 存储&#xff08;Web Storage&#xff09;是 HTML5 引入的一种在用户浏览器中存储数据的机制。它提供了比传统的 cookies 更加方便和强大的功能&#xff0c;包括更大的存储空间、更好的性能以及更简单的 API。Web 存储主要分为两种类型&#xff1a;localStorage 和 s…...

GCP Cloud Architect exam - PASS

备考指南 推荐视频课程 https://www.udemy.com/course/google-cloud-architect-certifications/?couponCodeKEEPLEARNING 推荐题库 https://www.udemy.com/course/gcp-professional-cloud-architect-exam-practice-tests-2024​/?couponCodeKEEPLEARNING 错题集 http…...

【Sentinel】初识Sentinel

目录 1.1.雪崩问题及解决方案 1.1.1.雪崩问题 1.1.2.超时处理 1.1.3.仓壁模式 1.1.4.断路器 1.1.5.限流 1.1.6.总结 1.2.服务保护技术对比 1.3.Sentinel介绍和安装 1.3.1.初识Sentinel 1.3.2.安装Sentinel 1.4.微服务整合Sentinel 1.1.雪崩问题及解决方案 1.1.1.…...

java常见类库

StringBuffer类 String和StringBuffer的区别 String 不可变性&#xff1a;String 类是不可变的&#xff0c;这意味着一旦创建了一个 String 对象&#xff0c;其值就不能改变。每次对 String 进行修改&#xff08;如连接、替换等操作&#xff09;都会产生新的 String 对象&…...

【CSS position 属性】static、relative、fixed、absolute 、sticky详细介绍,多层嵌套定位示例

文章目录 ★ position 的五种类型及基本用法 ★ 一、position 属性概述 二、position 的五种类型详解(初学者版) 1. static(默认值) 2. relative(相对定位) 3. absolute(绝对定位) 4. fixed(固定定位) 5. sticky(粘性定位) 三、定位元素的层级关系(z-i…...

python爬虫:Newspaper3k 的详细使用(好用的新闻网站文章抓取和解析的Python库)

更多内容请见: 爬虫和逆向教程-专栏介绍和目录 文章目录 一、Newspaper3k 概述1.1 Newspaper3k 介绍1.2 主要功能1.3 典型应用场景1.4 安装二、基本用法2.2 提取单篇文章的内容2.2 处理多篇文档三、高级选项3.1 自定义配置3.2 分析文章情感四、实战案例4.1 构建新闻摘要聚合器…...

DBAPI如何优雅的获取单条数据

API如何优雅的获取单条数据 案例一 对于查询类API&#xff0c;查询的是单条数据&#xff0c;比如根据主键ID查询用户信息&#xff0c;sql如下&#xff1a; select id, name, age from user where id #{id}API默认返回的数据格式是多条的&#xff0c;如下&#xff1a; {&qu…...

【C语言练习】080. 使用C语言实现简单的数据库操作

080. 使用C语言实现简单的数据库操作 080. 使用C语言实现简单的数据库操作使用原生APIODBC接口第三方库ORM框架文件模拟1. 安装SQLite2. 示例代码:使用SQLite创建数据库、表和插入数据3. 编译和运行4. 示例运行输出:5. 注意事项6. 总结080. 使用C语言实现简单的数据库操作 在…...

网络编程(UDP编程)

思维导图 UDP基础编程&#xff08;单播&#xff09; 1.流程图 服务器&#xff1a;短信的接收方 创建套接字 (socket)-----------------------------------------》有手机指定网络信息-----------------------------------------------》有号码绑定套接字 (bind)--------------…...

Sklearn 机器学习 缺失值处理 获取填充失值的统计值

💖亲爱的技术爱好者们,热烈欢迎来到 Kant2048 的博客!我是 Thomas Kant,很开心能在CSDN上与你们相遇~💖 本博客的精华专栏: 【自动化测试】 【测试经验】 【人工智能】 【Python】 使用 Scikit-learn 处理缺失值并提取填充统计信息的完整指南 在机器学习项目中,数据清…...

微服务通信安全:深入解析mTLS的原理与实践

&#x1f525;「炎码工坊」技术弹药已装填&#xff01; 点击关注 → 解锁工业级干货【工具实测|项目避坑|源码燃烧指南】 一、引言&#xff1a;微服务时代的通信安全挑战 随着云原生和微服务架构的普及&#xff0c;服务间的通信安全成为系统设计的核心议题。传统的单体架构中&…...

聚六亚甲基单胍盐酸盐市场深度解析:现状、挑战与机遇

根据 QYResearch 发布的市场报告显示&#xff0c;全球市场规模预计在 2031 年达到 9848 万美元&#xff0c;2025 - 2031 年期间年复合增长率&#xff08;CAGR&#xff09;为 3.7%。在竞争格局上&#xff0c;市场集中度较高&#xff0c;2024 年全球前十强厂商占据约 74.0% 的市场…...

前端工具库lodash与lodash-es区别详解

lodash 和 lodash-es 是同一工具库的两个不同版本&#xff0c;核心功能完全一致&#xff0c;主要区别在于模块化格式和优化方式&#xff0c;适合不同的开发环境。以下是详细对比&#xff1a; 1. 模块化格式 lodash 使用 CommonJS 模块格式&#xff08;require/module.exports&a…...

Python爬虫(52)Scrapy-Redis分布式爬虫架构实战:IP代理池深度集成与跨地域数据采集

目录 一、引言&#xff1a;当爬虫遭遇"地域封锁"二、背景解析&#xff1a;分布式爬虫的两大技术挑战1. 传统Scrapy架构的局限性2. 地域限制的三种典型表现 三、架构设计&#xff1a;Scrapy-Redis 代理池的协同机制1. 分布式架构拓扑图2. 核心组件协同流程 四、技术实…...