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

利用编程思维做题之最小堆选出最大的前10个整数

1. 理解问题

        我们需要设计一个程序,读取 80,000 个无序的整数,并将它们存储在顺序表(数组)中。然后从这些整数中选出最大的前 10 个整数,并打印它们。要求我们使用时间复杂度最低的算法。

        由于数据量很大,直接排序的时间复杂度较高,因此我们需要一个更高效的算法。最小堆 是一种合适的选择,因为它能够在 O(n log k) 的时间复杂度内完成最大 10 个整数的选取。

2. 输入输出

  • 输入:通过键盘输入 80,000 个整数。
  • 输出:打印出最大的 10 个整数。

3. 数据结构

        我们使用一个最小堆来存储当前最大 10 个数。堆的根节点是堆中最小的元素,插入新元素时,如果新元素大于堆的根节点则替换根节点并调整堆结构。这样,在遍历完所有 80,000 个数之后,堆中的 10 个元素就是最大的 10 个整数。

        最小堆的数据结构如下:

struct MinHeap {
    int* arr;     // 存储堆的数组
    int size;     // 当前堆的大小
    int capacity; // 堆的最大容量
};

4. 制定策略

  1. 建堆:我们通过一个大小为 10 的最小堆来存储当前最大的 10 个数。
  2. 遍历输入:每读取一个数,检查该数是否大于堆顶元素,如果大于,则替换堆顶并调整堆。
  3. 输出结果:遍历完所有数后,堆中将包含最大的 10 个数。
  4. 时间复杂度:由于堆的操作是 O(log k),每次插入操作的时间复杂度为 O(log 10),因此整个过程的时间复杂度是 O(n log 10) ≈ O(n)。

5. 实现代码

5.1 完整代码

#include <stdio.h>
#include <stdlib.h>

// 最小堆的结构体定义
struct MinHeap {
    int* arr;     // 存储堆的数组
    int size;     // 当前堆的大小,即有数值的个数
    int capacity; // 堆的最大容量
};

// 创建最小堆
struct MinHeap* createMinHeap(int capacity) {
    // 定义一个MinHeap结构体大小的指针,指向一个堆
    struct MinHeap* heap = (struct MinHeap*)malloc(sizeof(struct MinHeap));
    heap->arr = (int*)malloc(sizeof(int) * capacity);
    heap->size = 0;
    heap->capacity = capacity;
    return heap;
}

// 交换两个元素
void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

// 维护堆的性质(向下调整)
void heapify(struct MinHeap* heap, int index) {
    int left = 2 * index + 1;
    int right = 2 * index + 2;
    int smallest = index;

    // 找出最小的元素
    if (left < heap->size && heap->arr[left] < heap->arr[smallest]) {
        smallest = left;
    }
    if (right < heap->size && heap->arr[right] < heap->arr[smallest]) {
        smallest = right;
    }

    // 如果最小元素不是当前元素,交换并继续调整
    if (smallest != index) {
        swap(&heap->arr[index], &heap->arr[smallest]);
        heapify(heap, smallest);
    }
}

// 维护堆的性质(向上调整)
void upheapify(struct MinHeap* heap, int index) {
    while (index > 0 && heap->arr[index] < heap->arr[(index - 1) / 2]) {
        swap(&heap->arr[index], &heap->arr[(index - 1) / 2]);
        index = (index - 1) / 2;
    }
}

// 插入元素到堆中
void insert(struct MinHeap* heap, int value) {
    if (heap->size < heap->capacity) {
        // 如果堆未满,直接插入
        heap->arr[heap->size] = value;
        upheapify(heap, heap->size);  // 插入后需要向上调整
        heap->size++;
    } else if (value > heap->arr[0]) {
        // 如果堆已满且当前值大于堆顶元素,则替换堆顶
        heap->arr[0] = value;
        heapify(heap, 0);  // 替换堆顶后需要进行堆化
    }
}

// 打印堆中的前 10 个最大值
void printTop10(struct MinHeap* heap) {
    // 最小堆中的前 10 个最大值已经存储在堆中,直接打印
    for (int i = 0; i < heap->size; i++) {
        printf("%d ", heap->arr[i]);
    }
    printf("\n");
}

// 主程序
int main() {
    struct MinHeap* heap = createMinHeap(10); // 创建一个容量为 10 的最小堆
    int value;

    printf("请输入 80000 个整数(每输入一个整数后按 Enter,输入 80000 个数):\n");

    // 读取 80,000 个整数
    for (int i = 0; i < 80000; i++) {
        scanf("%d", &value);
        insert(heap, value); // 将输入的值插入堆中
    }

    // 打印堆中的前 10 个最大值
    printf("最大的 10 个整数是:\n");
    printTop10(heap);

    // 释放堆内存
    free(heap->arr);
    free(heap);

    return 0;
}
 

6. 代码说明

  • 结构体定义:我们定义了一个 MinHeap 结构体来表示最小堆,包含一个数组 arr 存储堆的元素,size 表示当前堆的大小,capacity 是堆的最大容量(即 10)。
  • 堆的操作
    • createMinHeap:创建一个新的最小堆。
    • swap:交换堆中的两个元素。
    • heapify:维护堆的性质,确保堆仍然是最小堆。
    • insert:将新元素插入堆。如果堆未满,直接插入。如果堆已满并且新元素大于堆顶元素,则替换堆顶并重新调整堆。
    • printTop10:打印堆中的前 10 个最大值(即堆中的元素)。
  • 主程序
    • 通过 scanf 读取 80,000 个整数,并将它们插入最小堆。
    • 插入操作将保证堆中始终保存着最大的 10 个元素。
    • 最后输出堆中的元素,即为最大的 10 个整数。

7. 模拟过程

假设输入为:

2 5 8 12 20 10 1 35 27 50 41 39 70 80 90 23 17 16 13 11 ...

程序将使用最小堆的结构,维护堆中最大 10 个数。每读取一个新数,程序将插入最小堆,并保证堆的大小不超过 10。当所有 80,000 个数输入完成后,堆中将包含最大的 10 个数。

8. 运行结果

        假设输入的数据中最大的 10 个数为:90, 80, 70, 50, 41, 39, 35, 27, 23, 20,程序输出:

        最大的 10 个整数是:90 80 70 50 41 39 35 27 23 20 

        注意,此代码只会获取最大的10个数,但不会排序这10个数。

9. 时间和空间复杂度分析

  • 时间复杂度
    • 建堆的时间复杂度:每次插入一个元素时,最小堆的插入操作为 O(log 10) = O(1),因此整个过程的时间复杂度是 O(n),其中 n 为 80,000。
  • 空间复杂度:最小堆需要 O(10) 的空间来存储最大 10 个数,因此空间复杂度为 O(1),即常数空间。

10. 总结

        通过使用最小堆,我们能够以 O(n) 的时间复杂度找到并输出最大的 10 个数。这种方法比直接排序更高效,尤其是当数据量很大时。

相关文章:

利用编程思维做题之最小堆选出最大的前10个整数

1. 理解问题 我们需要设计一个程序&#xff0c;读取 80,000 个无序的整数&#xff0c;并将它们存储在顺序表&#xff08;数组&#xff09;中。然后从这些整数中选出最大的前 10 个整数&#xff0c;并打印它们。要求我们使用时间复杂度最低的算法。 由于数据量很大&#xff0c;直…...

详解MVC架构与三层架构以及DO、VO、DTO、BO、PO | SpringBoot基础概念

&#x1f64b;大家好&#xff01;我是毛毛张! &#x1f308;个人首页&#xff1a; 神马都会亿点点的毛毛张 今天毛毛张分享的是SpeingBoot框架学习中的一些基础概念性的东西&#xff1a;MVC结构、三层架构、POJO、Entity、PO、VO、DO、BO、DTO、DAO 文章目录 1.架构1.1 基本…...

Unity C# 影响性能的坑点

c用的时间长了怕unity的坑忘了&#xff0c;记录一下。 GetComponent最好使用GetComponent<T>()的形式&#xff0c; 继承自Monobehaviour的函数要避免空的Awake()、Start()、Update()、FixedUpdate().这些空回调会造成性能浪费 GetComponent方法最好避免在Update当中使用…...

工作学习:切换git账号

概括 最近工作用的git账号下发下来了&#xff0c;需要切换一下使用的账号。因为是第一次弄&#xff0c;不熟悉&#xff0c;现在记录一下。 打开设置 路径–git—git remotes&#xff0c;我这里选择项是Manage Remotes&#xff0c;点进去就可以了。 之后会出现一个输入框&am…...

量化交易系统开发-实时行情自动化交易-8.量化交易服务平台(一)

19年创业做过一年的量化交易但没有成功&#xff0c;作为交易系统的开发人员积累了一些经验&#xff0c;最近想重新研究交易系统&#xff0c;一边整理一边写出来一些思考供大家参考&#xff0c;也希望跟做量化的朋友有更多的交流和合作。 接下来会对于收集整理的33个量化交易服…...

Scala习题

姓名&#xff0c;语文&#xff0c;数学&#xff0c;英语 张伟&#xff0c;87&#xff0c;92&#xff0c;88 李娜&#xff0c;90&#xff0c;85&#xff0c;95 王强&#xff0c;78&#xff0c;90&#xff0c;82 赵敏&#xff0c;92&#xff0c;88&#xff0c;91 孙涛&#xff0c…...

结构方程模型(SEM)入门到精通:lavaan VS piecewiseSEM、全局估计/局域估计;潜变量分析、复合变量分析、贝叶斯SEM在生态学领域应用

目录 第一章 夯实基础 R/Rstudio简介及入门 第二章 结构方程模型&#xff08;SEM&#xff09;介绍 第三章 R语言SEM分析入门&#xff1a;lavaan VS piecewiseSEM 第四章 SEM全局估计&#xff08;lavaan&#xff09;在生态学领域高阶应用 第五章 SEM潜变量分析在生态学领域…...

OpenCV图像基础处理:通道分离与灰度转换

在计算机视觉处理中&#xff0c;理解图像的颜色通道和灰度表示是非常重要的基础知识。今天我们通过Python和OpenCV来探索图像的基本组成。 ## 1. 图像的基本组成 在数字图像处理中&#xff0c;彩色图像通常由三个基本颜色通道组成&#xff1a; - 蓝色&#xff08;Blue&#x…...

C++ 类和对象(类型转换、static成员)

目录 一、前言 二、正文 1.隐式类型转换 1.1隐式类型转换的使用 2.static成员 2.1 static 成员的使用 2.1.1static修辞成员变量 2.1.2 static修辞成员函数 三、结语 一、前言 大家好&#xff0c;我们又见面了。昨天我们已经分享了初始化列表&#xff1a;https://blog.c…...

【网络安全设备系列】12、态势感知

0x00 定义&#xff1a; 态势感知&#xff08;Situation Awareness&#xff0c;SA&#xff09;能够检测出超过20大类的云上安全风险&#xff0c;包括DDoS攻击、暴力破解、Web攻击、后门木马、僵尸主机、异常行为、漏洞攻击、命令与控制等。利用大数据分析技术&#xff0c;态势感…...

Linux介绍与安装指南:从入门到精通

1. Linux简介 1.1 什么是Linux&#xff1f; Linux是一种基于Unix的操作系统&#xff0c;由Linus Torvalds于1991年首次发布。Linux的核心&#xff08;Kernel&#xff09;是开源的&#xff0c;允许任何人自由使用、修改和分发。Linux操作系统通常包括Linux内核、GNU工具集、图…...

BGE-M3模型结合Milvus向量数据库强强联合实现混合检索

在基于生成式人工智能的应用开发中&#xff0c;通过关键词或语义匹配的方式对用户提问意图进行识别是一个很重要的步骤&#xff0c;因为识别的精准与否会影响后续大语言模型能否检索出合适的内容作为推理的上下文信息&#xff08;或选择合适的工具&#xff09;以给出用户最符合…...

鸿蒙NEXT开发案例:文字转拼音

【引言】 在鸿蒙NEXT开发中&#xff0c;文字转拼音是一个常见的需求&#xff0c;本文将介绍如何利用鸿蒙系统和pinyin-pro库实现文字转拼音的功能。 【环境准备】 • 操作系统&#xff1a;Windows 10 • 开发工具&#xff1a;DevEco Studio NEXT Beta1 Build Version: 5.0.…...

CTF之密码学(栅栏加密)

栅栏密码是古典密码的一种&#xff0c;其原理是将一组要加密的明文划分为n个一组&#xff08;n通常根据加密需求确定&#xff0c;且一般不会太大&#xff0c;以保证密码的复杂性和安全性&#xff09;&#xff0c;然后取每个组的第一个字符&#xff08;有时也涉及取其他位置的字…...

修改插槽样式,el-input 插槽 append 的样式

需缩少插槽 append 的 宽度 方法1、使用内联样式直接修改&#xff0c;指定 width 为 30px <el-input v-model"props.applyBasicInfo.outerApplyId" :disabled"props.operateCommandType input-modify"><template #append><el-button click…...

UPLOAD LABS | PASS 01 - 绕过前端 JS 限制

关注这个靶场的其它相关笔记&#xff1a;UPLOAD LABS —— 靶场笔记合集-CSDN博客 0x01&#xff1a;过关流程 本关的目标是上传一个 WebShell 到目标服务器上&#xff0c;并成功访问&#xff1a; 我们直接尝试上传后缀为 .php 的一句话木马&#xff1a; 如上&#xff0c;靶场弹…...

【css实现收货地址下边的平行四边形彩色线条】

废话不多说&#xff0c;直接上代码&#xff1a; <div class"address-block" ><!-- 其他内容... --><div class"checked-ar"></div> </div> .address-block{height:120px;position: relative;overflow: hidden;width: 500p…...

缓存方案分享

不知道大家平常更新缓存是怎么做的&#xff0c;但是大部分时候都是更新数据的同时更新缓存&#xff0c;今天和同事一起聊到一个缓存方案的问题&#xff0c;感觉很有趣、非常精妙&#xff0c;记录一下。 基于此本文将介绍几种常见的缓存更新策略&#xff0c;包括简单的缓存覆盖…...

第四十篇 DDP模型并行

摘要 分布式数据并行(DDP)技术是深度学习领域中的一项重要技术,它通过将数据和计算任务分布在多个计算节点上,实现了大规模模型的并行训练。 DDP技术的基本原理是将数据和模型参数分割成多个部分,每个部分由一个计算节点负责处理。在训练过程中,每个节点独立计算梯度,…...

软件测试面试之常规问题

1.描述一下测试过程 类似题目:测试的生命周期 思路:这是一个“范围”很大的题目&#xff0c;而且回答时间一般在3分钟之内&#xff0c;不可能非常详细的描述整个过程&#xff0c;因此答题的思路要从整体结构入手&#xff0c;不要过细。为了保证答案的准确性&#xff0c;可以引…...

IGP(Interior Gateway Protocol,内部网关协议)

IGP&#xff08;Interior Gateway Protocol&#xff0c;内部网关协议&#xff09; 是一种用于在一个自治系统&#xff08;AS&#xff09;内部传递路由信息的路由协议&#xff0c;主要用于在一个组织或机构的内部网络中决定数据包的最佳路径。与用于自治系统之间通信的 EGP&…...

全球首个30米分辨率湿地数据集(2000—2022)

数据简介 今天我们分享的数据是全球30米分辨率湿地数据集&#xff0c;包含8种湿地亚类&#xff0c;该数据以0.5X0.5的瓦片存储&#xff0c;我们整理了所有属于中国的瓦片名称与其对应省份&#xff0c;方便大家研究使用。 该数据集作为全球首个30米分辨率、覆盖2000–2022年时间…...

oracle与MySQL数据库之间数据同步的技术要点

Oracle与MySQL数据库之间的数据同步是一个涉及多个技术要点的复杂任务。由于Oracle和MySQL的架构差异&#xff0c;它们的数据同步要求既要保持数据的准确性和一致性&#xff0c;又要处理好性能问题。以下是一些主要的技术要点&#xff1a; 数据结构差异 数据类型差异&#xff…...

AI书签管理工具开发全记录(十九):嵌入资源处理

1.前言 &#x1f4dd; 在上一篇文章中&#xff0c;我们完成了书签的导入导出功能。本篇文章我们研究如何处理嵌入资源&#xff0c;方便后续将资源打包到一个可执行文件中。 2.embed介绍 &#x1f3af; Go 1.16 引入了革命性的 embed 包&#xff0c;彻底改变了静态资源管理的…...

蓝桥杯 冶炼金属

原题目链接 &#x1f527; 冶炼金属转换率推测题解 &#x1f4dc; 原题描述 小蓝有一个神奇的炉子用于将普通金属 O O O 冶炼成为一种特殊金属 X X X。这个炉子有一个属性叫转换率 V V V&#xff0c;是一个正整数&#xff0c;表示每 V V V 个普通金属 O O O 可以冶炼出 …...

20个超级好用的 CSS 动画库

分享 20 个最佳 CSS 动画库。 它们中的大多数将生成纯 CSS 代码&#xff0c;而不需要任何外部库。 1.Animate.css 一个开箱即用型的跨浏览器动画库&#xff0c;可供你在项目中使用。 2.Magic Animations CSS3 一组简单的动画&#xff0c;可以包含在你的网页或应用项目中。 3.An…...

08. C#入门系列【类的基本概念】:开启编程世界的奇妙冒险

C#入门系列【类的基本概念】&#xff1a;开启编程世界的奇妙冒险 嘿&#xff0c;各位编程小白探险家&#xff01;欢迎来到 C# 的奇幻大陆&#xff01;今天咱们要深入探索这片大陆上至关重要的 “建筑”—— 类&#xff01;别害怕&#xff0c;跟着我&#xff0c;保准让你轻松搞…...

Caliper 负载(Workload)详细解析

Caliper 负载(Workload)详细解析 负载(Workload)是 Caliper 性能测试的核心部分,它定义了测试期间要执行的具体合约调用行为和交易模式。下面我将全面深入地讲解负载的各个方面。 一、负载模块基本结构 一个典型的负载模块(如 workload.js)包含以下基本结构: use strict;/…...

wpf在image控件上快速显示内存图像

wpf在image控件上快速显示内存图像https://www.cnblogs.com/haodafeng/p/10431387.html 如果你在寻找能够快速在image控件刷新大图像&#xff08;比如分辨率3000*3000的图像&#xff09;的办法&#xff0c;尤其是想把内存中的裸数据&#xff08;只有图像的数据&#xff0c;不包…...

LangFlow技术架构分析

&#x1f527; LangFlow 的可视化技术栈 前端节点编辑器 底层框架&#xff1a;基于 &#xff08;一个现代化的 React 节点绘图库&#xff09; 功能&#xff1a; 拖拽式构建 LangGraph 状态机 实时连线定义节点依赖关系 可视化调试循环和分支逻辑 与 LangGraph 的深…...