TopK问题的三种解法

2023-10-26

TopK问题是指从n个数据中取前K个数据,在生活中的应用也有很多,如游戏中xxx的排行榜前10名等。在这篇博客中我将主要利用去解决TopK问题。

堆排序

首先我们需要建一个堆,然后我们再进行堆排序,排好序后直接取前K个就可以了。需要注意的是在使用堆排序的时候,我们需要确定我们要排升序还是降序。如果是升序的话,我们要建一个大根堆;如果是降序的话,我们要建一个小根堆思路:(可以结合图来进行分析) 这里我们以排降序为例子进行说明,建好小根堆后,我们将堆顶元素与堆中的最后一个元素进行互换   (让最小的元素换到最后面,以此来达到降序),此时最后一个元素就是最小的那个元素了,然后让堆的大小 - 1,也就是我们将最后一个元素从堆中踢出,可以将它看做已排好序的一个集合。然后再对这个堆进行向下调整算法,重新让它成为一个小根堆,然后重复这段操作,直到堆中只剩1个元素。堆排序的时间复杂度为O(n*logn)。

//向下调整算法
void AdjustDown(int* a, int n, int root)
{
	int parent = root;
	int child = 2 * parent + 1;

	while (child < n)
	{
		//左孩子和右孩子进行比较,选出较小的【如果没有右孩子,不进行该比较】
		if (child + 1 < n && a[child] > a[child + 1])
		{
			child++;
		}
		//判断孩子节点和父节点【调成小堆】
		if (a[child] < a[parent])
		{
			int tmp = a[child];
			a[child] = a[parent];
			a[parent] = tmp;

			parent = child;
			child = 2 * child + 1;
		}
		else
		{
			break;
		}
	}
}

void HeapCreate(Heap* hp, HpDataType* a, int sz)
{
	//堆的空间开辟和初始化
	hp->_a = (HpDataType*)malloc(sizeof(HpDataType)*sz);
	hp->_size = sz;
	hp->_capacity = sz;
	//数据的拷贝
	memcpy(hp->_a, a, sizeof(HpDataType)*sz);

	//堆的创建
	int i = 0;
	for (i = (sz - 1 - 1) / 2;i >= 0;--i)
	{
		AdjustDown(hp->_a, sz, i);
	}
}

void HeapSort(Heap* hp)
{
	int i = 0;
	for (i = hp->_size - 1; i > 0;--i)
	{
		Swap(&hp->_a[i], &hp->_a[0]);
		AdjustDown(hp->_a, i, 0);
	}
}

void PrintTopK(int* a, int n, int K)
{
	Heap hp;
	HeapCreate(&hp, a, K);
	HeapSort(&hp);

	int i = 0;
	for (i = 0; i < K; ++i)
	{
		printf("%d ", hp._a[i]);
	}
}

建一个大小为n的堆

我们利用所给的n个数据去建一个大小为n的堆,如果求的是最大的K个数据,那么我们需要建大根堆;要求最小的K个数据,我们要建小根堆。这里我们以求最大的K个数据为例子,我们建一个大小为n的大根堆,然后这个堆的堆顶元素(HeapTop),然后再对将堆顶元素进行删除(HeapPop)的操作,然后再进行向下调整算法。要求最大的K个,那么只要循环K次即可。

HpDataType HeapTop(Heap* hp)
{
	return hp->_a[0];
}

void HeapPop(Heap* hp)
{
	Swap(&hp->_a[0], &hp->_a[hp->_size - 1]);
	hp->_size--;
    //每进行完1次删除,都要进行1次向下调整
	AdjustDown(hp->_a, hp->_size, 0);
}

void PrintTopK(int* a, int n, int K)
{
	Heap hp;
	HeapCreate(&hp, a, K);

	int i = 0;
	for (i = 0; i < K; ++i)
	{
		printf("%d ", HeapTop(&hp));
		HeapPop(&hp);
	}
}

建一个大小为K的堆

这里我们以求最大的K个数据为例子。首先,我们先用一组数据中的前K个数据建一个小根堆,然后依次的用剩下的数据与小根堆的堆顶元素进行比较,如果该元素大于堆顶元素,那么将该元素替换为堆顶元素,随后再进行向下调整,使其保持小根堆,当所有元素都比较完后,小根堆中的K个元素就是这些数据中的最大的K个元素了。

void PrintTopK(int* a, int n, int K)
{
	Heap hp;
    //用前K个元素去建一个小根堆
	HeapCreate(&hp, a, K);

    //用剩下的元素与堆顶元素进行比较
	int i = 0;
	for (i = K; i < n; ++i)
	{
		if (a[i] > HeapTop(&hp))
		{
			hp._a[0] = a[i];//替换堆顶元素
 			AdjustDown(hp._a, K, 0);
		}
	}
	for (i = 0; i < K;++i)
	{
		printf("%d ", hp._a[i]);
	}
}

 

本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)

TopK问题的三种解法 的相关文章

  • 标准的遗传算法求函数最大值

    最近看了下遗传算法 刚看了一点 就觉得手痒 非要把程序编制出来看看效果 我现在总认为那些理论再高深 无法用计算机实现就是空话 呵呵 下面是我调试了好久的代码 无赖没有学过数据结构 算法 程序写的很差 单效果还是出来了 高兴 和大家共同分享下
  • 动态规划系列之「最长递增子序列的个数」

    673 最长递增子序列的个数 给定一个未排序的整数数组 找到最长递增子序列的个数 示例 1 输入 1 3 5 4 7 输出 2 解释 有两个最长递增子序列 分别是 1 3 4 7 和 1 3 5 7 示例 2 输入 2 2 2 2 2 输出
  • 数据结构 —七大排序算法(图文详细版)

    文章目录 前言 一 插入排序 1 直接插入排序 1 原理 2 实现 3 稳定性 时间复杂度 2 希尔排序 1 原理 2 具体实现 3 稳定性 时间复杂度 二 选择排序 1 直接选择排序 1 原理 2 具体实现 3 稳定性 时间复杂度 4 优
  • 数据结构与算法:遍历二叉树

    二叉树遍历原理 二叉树的遍历 traversing binary tree 是指从根结点出发 按照某种次序依次访问二叉树中所有结点 使得每个结点被访问一次且仅被访问一次 这里有两个关键词 访问和次序 二叉树遍历方法 二叉树的遍历方式可以很多
  • JavaScript 算法系列---动态规划

    很久之前接触过这样一道题目 总共有十层阶梯 从1层开始往上爬 每次可以上1层或者2层 问到10层总共有多少种方法 思路 这个问题就是动态规划的一个经典例子 所谓动态规划 就是把复杂的问题进行拆解 拆解成一个个子问题 而这类问题最后非常适合使
  • 数据结构与算法:去除重复字母

    给你一个仅包含小写字母的字符串 请你去除字符串中重复的字母 使得每个字母只出现一次 需保证返回结果的字典序最小 要求不能打乱其他字符的相对位置 示例 1 输入 bcabc 输出 abc 示例 2 输入 cbacdcbc 输出 acdb 解题
  • 最短路径(Dijkstra)算法

    目录 一 Dijkstra算法 二 核心思路 三 步骤 四 代码 一 Dijkstra算法 迪杰斯特拉 Dijkstra 算法是由荷兰计算机科学家狄克斯特拉于1959年提出的 是寻找从一个顶点到其余各顶点的最短路径算法 可用来解决最短路径问
  • 数据结构-判断平衡二叉树(java)

    判断平衡二叉树 题目 力扣110题 解题思路 1 首先理解平衡二叉树的定义 使用Map存储每个节点的高度 2 求得当前节点的左右子树高度 若Map中左右子树高度已经求过 直接取得 若没有 通过递归计算高度并存入Map中 3 左右子树高度差
  • 环形链表II

    环形链表II 给定一个链表的头节点 head 返回链表开始入环的第一个节点 如果链表无环 则返回 null 如果链表中有某个节点 可以通过连续跟踪 next 指针再次到达 则链表中存在环 为了表示给定链表中的环 评测系统内部使用整数 pos
  • 【通俗易懂-动态图解析】归并排序、计数排序

    编程TWO 编程小兔崽 今天 归并排序 和选择排序一样 归并排序的性能不受输入数据的影响 但表现比选择排序好的多 因为始终都是O n log n 的时间复杂度 代价是需要额外的内存空间 归并排序是建立在归并操作上的一种有效的排序算法 该算法
  • 数据结构与算法:线索二叉树

    线索二叉树 线索二叉树原理 首先我们要来看看这空指针有多少个呢 对于一个有n个结点的二叉链表 每个结点有指向左右孩子的两个指针域 所以一共是2n个指针域 而n个结点的二叉树一共有n 1条分支线数 也就是说 其实是存在2n n 1 n 1个空
  • 二叉树-判断另一棵树的子树(Java)

    另一棵的子树 力扣572题 题目 给你两棵二叉树 root 和 subRoot 检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树 如果存在 返回 true 否则 返回 false 二叉树 tree 的一棵子树包括 t
  • 【算法】分治、动态规划和贪心算法

    这三种算法非常相似 但是又有一些区别 理解如下 分治 把一个问题划分为若干子问题 求出子问题的最优解 再把子问题的最优解进行merge 最终得到原问题的最优解 动态规划 原问题的最优解包含子问题的最优解 即 拥有最优子结构 同时 求子问题的
  • 二叉查找树实现

    package leetcode May import java util ArrayList import java util List description 二叉查找树 author qiangyuecheng date 2022 5
  • 最小生成树总结1 prim算法

    最小生成树总结1 prim算法 最小生成树总结2 kurskal算法 文章目录 1 最小生成树问题概述 2 Prim算法流程 3 模板 4 板子题 1 最小生成树问题概述 给定带权节点网络 从中确定一个包含所有节点 n个 n 1条边 所有节
  • 递推典型算法:猴子爬山,跳台阶,爬楼梯(牛客网)、魔法深渊(快手)----Python、Java

    递推算法的基本思想是把一个复杂的 庞大的计算过程转化为简单过程的多次重复 其首要问题是得到相邻的数据项之间的关系 即递推关系 以猴子爬山为例 1 问题的提出 一个顽猴在一座有30级太假的小山上爬山活跃 猴子上一步可跳1级或者3级 试求上山的
  • 数据结构与算法:KMP模式匹配算

    KMP模式匹配算法原理 如果主串S abcdefgab 其实还可以更长一些 我们就省略掉只保留前9位 我们要匹配的T abcdex 那么如果用BF算法的话 前5个字母 两个串完全相等 直到第6个字母 f 与 x 不等 如图5 7 1的 所示
  • 排列数组使得偶数在奇数的前面

    Name ReorderOddEven c Author 齐保元 Version Copyright Your copyright notice Description Hello World in C Ansi style include
  • LSM详解

    关于LSM结构的相关介绍 这篇文章比较好 特此纪录一下https yq aliyun com articles 767772
  • ConcurrentHashMap源码解读

    曾经研究过jkd1 5新特性 其中ConcurrentHashMap就是其中之一 其特点 效率比Hashtable高 并发性比hashmap好 结合了两者的特点 集合是编程中最常用的数据结构 而谈到并发 几乎总是离不开集合这类高级数据结构的

随机推荐

  • java如何将null转化为空串也就是empty

    java如何将null转化为空串也就是empty 前言 在说转换之前 简单说一下它们之间的区别 如下 1 null不指向任何对象 相当于没有任何值 而 代表一个长度为0的字符串 2 null不分配内存空间 而 会分配内存空间 那如何将nul
  • HTTP 2.0 与HTTP1.1的差别

    前面的话 在说HTTP2 0前 先说一说发展到HTTP1 1做了哪些升级 推荐好文 一文读懂HTTP 2及HTTP 3特性 HTTP1 1的升级 目前使用最广泛的HTTP1 1做了哪些重大升级 默认长连接 HTTP1 0也提供长连接 但是默
  • 拓扑排序(广度优先搜索实现)

    有向无环图可以用来表示各种事物的顺序 比如工作顺序 一些事情必须在另一些事情完成之后才能开始进行 那么 为了获得正确的工作顺序 一件事情开始之前 必须保证它的前置条件全部满足 就需要用到拓扑排序 拓扑排序其实就是在有向无环图中 只要存在边
  • nvm 查看所有可以下载node的版本

    nvm 查看所有可以下载node的版本 nvm list 命令 显示版本列表 nvm list 显示已安装的版本 同 nvm list installed nvm list installed 显示已安装的版本 nvm list avail
  • 三阶段提交协议(3PC)

    3PC 主要是为了解决两阶段提交协议的单点故障问题和缩小参与者阻塞范围 引入参与节点的超时机制之外 3PC把2PC的准备阶段分成事务询问 该阶段不会阻塞 和事务预提交 则三个阶段分别为CanCommit PreCommit DoCommit
  • codeforces 526D(kmp,数学)

    description One day Om Nom found a thread with n beads of different colors He decided to cut the first several beads fro
  • 内核体系结构和编译体系分析

    1 Linux操作系统体系结构 1 操作系统可以分为两个层次 内核空间和用户空间 内核和用户空间使用不同的保护地址空间 内核不能将用户空间传递的地址进行直接的操作 需要先转换 2 系统调用 内核空间管理设备资源 应用程序通过内核提供的内核调
  • 米家接入HomeKit系列三:HomeAssistant接入米家网关

    系列文章 米家接入HomeKit系列一 接入基本原理与开篇 米家接入HomeKit系列二 通过群辉NAS的Docker搭建HomeAssistant 米家接入HomeKit系列三 HomeAssistant接入米家网关 米家接入HomeKi
  • 微信小程序--web-view--h5返回微信小程序

    1 配置微信小程序 web view 记得配置业务域名 微信公众平台配置业务域名 上线需要 1 1 建议微信小程序里单独用一个页面打开
  • debug

    1 在DOS提示符下 进入Debug程序 2 详细记录每一步所用的命令 以及查看结果的方法和具体结果 3 现有一个双字加法源程序如下 其中存在错误 现假设已汇编 连结生成了可执行文件HB EXE 存放在d MASM目录下 请使用Debug对
  • argmax与max的区别

    y max f x 表示y是函数f x 的最大值 y argmax f x 表示y为函数f x 取得最大值时 参数x的值 例 f x x3 x的取值范围是 0 1 2 3 y max f x 27 y argmax f x 3
  • AcWing 907. 区间覆盖 贪心

    AcWing 907 区间覆盖 给定N个闭区间 ai bi 以及一个线段区间 s t 请你选择尽量少的区间 将指定线段区间完全覆盖 输出最少区间数 如果无法完全覆盖则输出 1 输入格式 第一行包含两个整数s和t 表示给定线段区间的两个端点
  • 数据分析中的统计与机器学习应用

    1 数据分析应用场景 数据分析场景 例如逛淘宝 后台一般会从以下几个方面对用户数据进行分析来 了解的一个产品的数据模型 1 Acquisition 获取用户 运营一件产品首先就需要获取用户 也就是推广 运营人员要分析自己产品的特性以及想要推
  • 一文看懂PCB助焊层跟阻焊层的区别与作用

    一文看懂PCB助焊层跟阻焊层的区别与作用 PCBworld 今天 阻焊层简介 阻焊盘就是soldermask 是指板子上要上绿油的部分 实际上这阻焊层使用的是负片输出 所以在阻焊层的形状映射到板子上以后 并不是上了绿油阻焊 反而是露出了铜皮
  • zookeeper 搭建集群

    待完善
  • 《计算机文化基础》22-23第一学期后十周教学计划(中国铁道出版社第三版)

    课程 任课教师 授课班级 编制时间 计算机文化基础 2022 10 28 授课日期 2022年 10月31日至 2022年 12月 16日 本课程总课时 28课时 已授课时 0 课时 尚余课时 28课时 本学期授课周 7周 本学期周课时 4
  • 超详细讲解!Android面试题集2021版,面试心得体会

    前言 Android常用知识体系是什么鬼 所谓常用知识体系 就是指对项目中重复使用率较高的功能点进行梳理 注意哦 不是Android知识体系 古语道 学而不思则罔 思而不学则殆 如果将做项目类比为 学 那么整理就可以类比为 思 在做项目过程
  • 文件包含漏洞

    一 文件包含函数 将外部文件的内容引入当前环境 include
  • 玩转Kali之初始化系统

    文章目录 下载镜像 安装系统 修改root密码 配置APT国内源 更新软件包 下载镜像 1 打开kali官网 https www kali org 安装系统 1 打开VirtualBox 2 选择新建虚拟机 1 输入虚拟机名称 2 选择安装
  • TopK问题的三种解法

    TopK问题是指从n个数据中取前K个数据 在生活中的应用也有很多 如游戏中xxx的排行榜前10名等 在这篇博客中我将主要利用堆去解决TopK问题 堆排序 首先我们需要建一个堆 然后我们再进行堆排序 排好序后直接取前K个就可以了 需要注意的是