本文提供用建堆来解决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个数后排序,如想排序,可以用一下堆排序):文章来源:https://www.toymoban.com/news/detail-528034.html
文章来源地址https://www.toymoban.com/news/detail-528034.html
到了这里,关于【数据结构】---TopK问题的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!