当前位置: 首页 > 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 对象&…...

Go 语言接口详解

Go 语言接口详解 核心概念 接口定义 在 Go 语言中&#xff0c;接口是一种抽象类型&#xff0c;它定义了一组方法的集合&#xff1a; // 定义接口 type Shape interface {Area() float64Perimeter() float64 } 接口实现 Go 接口的实现是隐式的&#xff1a; // 矩形结构体…...

CentOS下的分布式内存计算Spark环境部署

一、Spark 核心架构与应用场景 1.1 分布式计算引擎的核心优势 Spark 是基于内存的分布式计算框架&#xff0c;相比 MapReduce 具有以下核心优势&#xff1a; 内存计算&#xff1a;数据可常驻内存&#xff0c;迭代计算性能提升 10-100 倍&#xff08;文档段落&#xff1a;3-79…...

Auto-Coder使用GPT-4o完成:在用TabPFN这个模型构建一个预测未来3天涨跌的分类任务

通过akshare库&#xff0c;获取股票数据&#xff0c;并生成TabPFN这个模型 可以识别、处理的格式&#xff0c;写一个完整的预处理示例&#xff0c;并构建一个预测未来 3 天股价涨跌的分类任务 用TabPFN这个模型构建一个预测未来 3 天股价涨跌的分类任务&#xff0c;进行预测并输…...

Java - Mysql数据类型对应

Mysql数据类型java数据类型备注整型INT/INTEGERint / java.lang.Integer–BIGINTlong/java.lang.Long–––浮点型FLOATfloat/java.lang.FloatDOUBLEdouble/java.lang.Double–DECIMAL/NUMERICjava.math.BigDecimal字符串型CHARjava.lang.String固定长度字符串VARCHARjava.lang…...

【JavaWeb】Docker项目部署

引言 之前学习了Linux操作系统的常见命令&#xff0c;在Linux上安装软件&#xff0c;以及如何在Linux上部署一个单体项目&#xff0c;大多数同学都会有相同的感受&#xff0c;那就是麻烦。 核心体现在三点&#xff1a; 命令太多了&#xff0c;记不住 软件安装包名字复杂&…...

Kafka入门-生产者

生产者 生产者发送流程&#xff1a; 延迟时间为0ms时&#xff0c;也就意味着每当有数据就会直接发送 异步发送API 异步发送和同步发送的不同在于&#xff1a;异步发送不需要等待结果&#xff0c;同步发送必须等待结果才能进行下一步发送。 普通异步发送 首先导入所需的k…...

数学建模-滑翔伞伞翼面积的设计,运动状态计算和优化 !

我们考虑滑翔伞的伞翼面积设计问题以及运动状态描述。滑翔伞的性能主要取决于伞翼面积、气动特性以及飞行员的重量。我们的目标是建立数学模型来描述滑翔伞的运动状态,并优化伞翼面积的设计。 一、问题分析 滑翔伞在飞行过程中受到重力、升力和阻力的作用。升力和阻力与伞翼面…...

在golang中如何将已安装的依赖降级处理,比如:将 go-ansible/v2@v2.2.0 更换为 go-ansible/@v1.1.7

在 Go 项目中降级 go-ansible 从 v2.2.0 到 v1.1.7 具体步骤&#xff1a; 第一步&#xff1a; 修改 go.mod 文件 // 原 v2 版本声明 require github.com/apenella/go-ansible/v2 v2.2.0 替换为&#xff1a; // 改为 v…...

Java后端检查空条件查询

通过抛出运行异常&#xff1a;throw new RuntimeException("请输入查询条件&#xff01;");BranchWarehouseServiceImpl.java // 查询试剂交易&#xff08;入库/出库&#xff09;记录Overridepublic List<BranchWarehouseTransactions> queryForReagent(Branch…...

Python学习(8) ----- Python的类与对象

Python 中的类&#xff08;Class&#xff09;与对象&#xff08;Object&#xff09;是面向对象编程&#xff08;OOP&#xff09;的核心。我们可以通过“类是模板&#xff0c;对象是实例”来理解它们的关系。 &#x1f9f1; 一句话理解&#xff1a; 类就像“图纸”&#xff0c;对…...