【数据结构】---TopK问题

这篇具有很好参考价值的文章主要介绍了【数据结构】---TopK问题。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

【数据结构】---TopK问题,【数据结构】知识篇+代码讲解,数据结构,leetcode

本文提供用建堆来解决TopK问题的一个思路

N个数中找出最大的或者最小的前k个

假设现从N个数中找最小的前k个

  • ①堆排序,时间复杂度O(N*logN),这N个数排一下序,前k个数就是需要的
  • ②建堆N个数的小堆,HeapPop k-1 次,就选出来了,因为小堆最小的在堆顶,选出一次后,再删除堆顶,向下调整法后又能选出次小的,然后再删除......N+(k-1) * logN ------->时间复杂度O(K*logN)
  • ③再优化:建k个数的堆来解决?找最小的前k个,建大堆思路:如果比堆顶要小,则替换堆顶的数据。假设N是10个亿,内存中存不下这些值(10亿个字节就是1G了,而10亿个整数就是4G了,放内存中建立数组是建不出来的,内存不够,即法1法2对于这种情况不适用),这些值在文件中,假设k是10。

OJ原题

从N个数中找出最小的前k个数

题述:

输入整数数组arr,找出其中最小的k个数。例如,输入4、5、1、6、2、7,3,9这8个数字,则最小的4个数字是1、2、3,4.

示例一:

输入:arr = 【3,2,1】,k = 2

输出:【1,2】或者【2,1】

示例二:

输入:arr = 【0,1,2,1】,k = 1

输出:【0】

思路:

问题一:

在N个数中找最小的前k个数,应该建大堆还是建小堆?答案:大堆,且建k个数的大堆,这k个数就是最小的前k个数。同理,如果在N个数中找最大的前k个数,应该建小堆。

问题二:

建大堆怎么找最小的前k个数?

大堆特性:堆顶是堆中的最大数,

①、从N个数中随机找k个数建一个大堆(建大堆就需要向下调整法)

②、将N个数中第k+1个数开始与堆的堆顶比较(因为前k个数据已拷贝到堆中了),如果比堆顶小,就直接替换堆顶,替换完一次就用一次向下调整法(因为你用一个更小的数来替换堆顶,那此时堆顶可能不满足大堆了,但它的左右子树满足大堆,就可用向下调整法,(用向下调整法是为了把刚才比堆顶小的数弄到下面,使堆顶还是堆的最大的一个),那么再次变为大堆,堆顶一定还是最大的,小的数一定会跑到下面,即其他的数在大堆中,都会被最小的前k个数挤出堆中,从第k+1个数开始一直跟堆中的数据比较到第N个数完事堆中就是最小的前k个数了

代码如下:

#define _CRT_SECURE_NO_WARNINGS 1

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

//为了选出最小的前k个数,所以用向下调整法建大堆
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++;
		}
		if (a[child] > a[parent])
		{//大堆的特性是父节点>孩子节点
			int tmp = a[child];
			a[child] = a[parent];
			a[parent] = tmp;

			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;//谨记向下调整法是在堆顶不满足堆的性质,而左右子树满足堆的性质时用的
		}
	}
}

/*Note: The returned array must be malloced, assume caller calls free()*/

int* getLeastNumbers(int* arr, int arrSize, int k, int* returnSize)
{
	*returnSize = k;
	if (k == 0)
	{
		return NULL;//如果k==0,说明一个数据都不需要,直接返回NULL就可以
	}
	//建立有k个数的数组,用动态开辟
	int* retNum = (int*)malloc(sizeof(int) * k);
	if (retNum == NULL)
	{
		printf("malloc fail\n");
		exit(-1);
	}
	memcpy(retNum, arr, sizeof(int) * k);//拷贝至动态数组,方便后续操作
	//我只要array数组的前k个,至于包不包含最小的前k个数都无所谓
	
	//数组建大堆(共k个数)
	for (int i = (k - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(retNum, k, i);
	}

	for (int j = k; j < arrSize; j++)
	{//从第k+1个数开始比较,因为前k个数已经拷贝到retNum堆中了
		if (arr[j] < retNum[0])
		{//如果数组中数据<堆顶,则替换堆顶
			retNum[0] = arr[j];
			AdjustDown(retNum, k, 0);
		}
	}

	return retNum;
}

int main()
{
	int arr[13] = { 1,4,6,7,8,34,2,5,67,8,6,7,9 };
	int LeastNumbersize = 0;
	int * tmp = getLeastNumbers(arr, 13, 5, &LeastNumbersize);
	printf("最小的前k个数:");
	for (int i = 0; i < LeastNumbersize; i++)
	{
		printf("%d ", tmp[i]);
	}
	return 0;
}

运行结果(因为题目没要求找出最小的前k个数后排序,如想排序,可以用一下堆排序):

【数据结构】---TopK问题,【数据结构】知识篇+代码讲解,数据结构,leetcode文章来源地址https://www.toymoban.com/news/detail-528034.html

到了这里,关于【数据结构】---TopK问题的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【数据结构】堆排序与TopK问题

    👀 樊梓慕: 个人主页   🎥 个人专栏: 《C语言》《数据结构》《蓝桥杯试题》《LeetCode刷题笔记》《实训项目》 🌝 每一个不曾起舞的日子,都是对生命的辜负 目录 前言  1.堆的概念和结构 2.堆的实现 2.1向上调整算法 2.2向下调整算法 2.3堆的创建 2.4建堆时间复杂度 2.5堆的

    2024年02月07日
    浏览(40)
  • 【数据结构】堆排序和TOPK问题

     😽 PREFACE 🎁欢迎各位→点赞👍 + 收藏⭐ + 评论📝 📢系列专栏:数据结构 🔊本专栏主要更新的是数据结构部分知识点 💪 种一棵树最好是十年前其次是现在 目录 0.利用堆的实现进行排序 1.堆排序 1.1 建堆 ​编辑  1.1.1 向上建堆 1.1.2 向下建堆 1.2 时间复杂度分析 1.3 堆排序

    2024年02月01日
    浏览(35)
  • 数据结构——堆的应用 Topk问题

    hello hello~ ,这里是大耳朵土土垚~💖💖 ,欢迎大家点赞🥳🥳关注💥💥收藏🌹🌹🌹 💥 个人主页:大耳朵土土垚的博客 💥 所属专栏:数据结构学习笔记 、C语言系列函数实现 💥对于数据结构顺序表、链表、堆有疑问的都可以在上面数据结构的专栏进行学习哦~ 有问题可

    2024年03月14日
    浏览(59)
  • 堆排序+TopK问题——“数据结构与算法”

    各位CSDN的uu们你们好呀,好久不见,停更了很长一段时间吧,最近小雅兰会开始慢慢更新起来的,下面,就进入小雅兰今天的分享的知识点吧,让我们一起进入堆的世界!!! 堆排序——(1) heap.h的内容: heap.c的内容: test.c的内容: 这样的堆排序其实也是可以的 但是有弊

    2024年02月13日
    浏览(49)
  • 【初阶数据结构】——堆排序和TopK问题

     ========================================================================= 个人主页 代码仓库 C语言专栏 初阶数据结构专栏 Linux专栏  ========================================================================= 接上篇二叉树和堆的引入 =========================================================================  目录 前言 建堆 插

    2024年02月07日
    浏览(44)
  • 玩转堆排序以及Topk问题——【数据结构】

    W...Y的主页 😊 代码仓库分享  💕 目录 堆排序  建堆  建堆的时间复杂度 Topk问题 学习了二叉树以及堆,今天我们来学习一下什么是堆排序以及经典二叉树问题——topk问题。 在学习开始我们先来回顾一下上篇博客中我们提到的堆,在实现堆时我们要进行向上调整或向下调

    2024年02月07日
    浏览(39)
  • 数据结构:堆的应用(堆排序和topk问题)

    个人主页 : 个人主页 个人专栏 : 《数据结构》 《C语言》 堆排序即是 先将数据建堆,再利用堆删除的思想来排序。 将待排序数组建堆 将堆顶数据与数组尾部数据交换 调整新的堆顶数据,使其保证堆的结构不变 重复2,3步直到堆中没有数据结束。 降序 建小堆 (父节点 小于

    2024年02月13日
    浏览(41)
  • 数据结构之树(Topk问题, 链式二叉树)

    取N个数中最大(小)的前k个值,N远大于k 这道题可以用堆的方法来解决,首先取这N个数的前k个值,用它们建堆 时间复杂度O(k) 之后将剩余的N-k个数据依次与堆顶数据进行比较,如果比堆顶数据大,则将堆顶数据覆盖后向下调整 时间复杂度(N-k)*log(N) 总共的时间复杂度为O(N*log(N)) 用数组

    2024年03月15日
    浏览(43)
  • 数据结构学习分享之堆的详解以及TopK问题

    💓博主CSDN主页:杭电码农-NEO💓   ⏩专栏分类:数据结构学习分享⏪   🚚代码仓库:NEO的学习日记🚚   🌹关注我🫵带你了解更多数据结构的知识   🔝🔝 本章就给大家带来久违的堆的知识,如果你还不知道数的相关知识,或者什么是完全二叉树,请跳转 树的介绍, 本章的堆结

    2024年02月05日
    浏览(109)
  • 【数据结构】长篇详解堆,堆的向上/向下调整算法,堆排序及TopK问题

    堆就是将一组数据所有元素按完全二叉树的顺序存储方式存储在一个 一维数组 中,并满足树中 每一个父亲节点都要大于其子节点 称为 大堆 (树中 每一个父亲节点都要大于其子节点 称为 小堆 )。 性质 ①对于大堆(大根堆)来说,堆的顶部也就是数组首元素一定是最大的元素 ②

    2024年02月07日
    浏览(42)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包