大佬教程收集整理的这篇文章主要介绍了数据结构--TopK问题,大佬教程大佬觉得挺不错的,现在分享给大家,也给大家做个参考。
●🧑个人主页:你帅你先说. ●📃欢迎点赞👍关注💡收藏💖 ●📖既选择了远方c;便只顾风雨兼程。 ●🤟欢迎大家有问题随时私信我! ●🧐版权:本文由[你帅你先说.]原创c;CSDN首发c;侵权必究。
什么是topK问题?简单来讲就是从n个数中取前k个最大的数。研究topK问题有什么价值吗? 这么说吧c;平常到了饭点你是不是得点外卖c;比如你今天要吃西餐c;那你就会在外卖系统中选择西餐一类c;系统就会帮你排出评分最高的几家店c;这就是topK问题。
思路一:@H_197_38@ 首先大多数人最先想到的一定是排序c;先排降序c;前k个数就是最大的c;假设我们用快速排序来排c;那么时间复杂度就是O(N*
l
o
g
2
log_2
log2N)c;但这种方法有点多此一举。我们只要前k个最大的c;没必要把所有数都排了。 在讲思路二前你可能需要去复习一下堆的内容→数据结构--二叉树
思路二:@H_197_38@ 可能有的人会想到之前二叉树讲的堆。N个数依次插入大堆c;Popk次c;每次取堆顶的数据就是前k个最大的数c;此时时间复杂度为O(N+k*
l
o
g
2
log_2
log2N) 思路三:@H_197_38@ 此时假设N非常大c;思路二可能就行不通了。为什么呢?因为内存可能存不下那么多数。那我们怎么做呢?首先c;用前k个数建立一个k个数的小堆c;再用剩下的N-K个数c;依次跟堆顶的数据进行比较c;如果比堆顶数据大c;就替换堆顶的数据c;再向下调整c;最后堆里面k个数就是最大的k个数。 此时时间复杂度为O(N*
l
o
g
2
K
log_2K
log2K)
结构定义@H_197_38@
typedef int HPDAtaType;
typedef struct Heap
{
HPDAtaType* a;
int size;
int capacity;
}HP;
堆的初始化@H_197_38@
void HeapInit(HP* hp)
{
assert(hp);
hp->a = NULL;
hp->size = hp->capacity = 0;
}
堆的向上调整@H_197_38@
void Adjustup(int* a, int child)
{
assert(a);
int parent = (child - 1) / 2;
while (child > 0)
{
if (a[child] < a[parent])
{
HPDAtaType tmp = a[child];
a[child] = a[parent];
a[parent] = tmp;
child = parent;
parent = (child - 1) / 2;
}
else
{
break;
}
}
}
堆的插入@H_197_38@
void HeapPush(HP* hp, HPDAtaType x)
{
assert(hp);
if (hp->size == hp->capacity)
{
size_t newCapacity = hp->capacity == 0 ? 4 : hp->capacity * 2;
HPDAtaType* tmp = realloc(hp->a, sizeof(HPDAtaType)*newCapacity);
if (tmp == NULL)
{
printf("realloc failn");
exit(-1);
}
hp->a = tmp;
hp->capacity = newCapacity;
}
hp->a[hp->size] = x;
hp->size++;
Adjustup(hp->a, hp->size - 1);
}
堆的向下调整@H_197_38@
void AdjustDown(int* a, int n, int parent)
{
int child = parent * 2 + 1;
while (child < n)
{
// 选出左右孩子中小的那一个
if (child + 1 < n && a[child + 1] < a[child])
{
++child;
}
// 如果小的孩子小于父亲c;则交换c;并继续向下调整
if (a[child] < a[parent])
{
Swap(&a[child], &a[parent]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
取堆顶元素@H_197_38@
HPDAtaType HeaPTOP(HP* hp)
{
assert(hp);
assert(!HeapEmpty(hp));
return hp->a[0];
}
堆的输出@H_197_38@
void HeapPrint(HP* hp)
{
for (int i = 0; i < hp->size; ++i)
{
printf("%d ", hp->a[i]);
}
printf("n");
}
堆的销毁@H_197_38@
void HeapDestroy(HP* hp)
{
assert(hp);
free(hp->a);
hp->capacity = hp->size = 0;
}
TopK实现@H_197_38@
void PrintTopK(int* a, int n, int k)
{
HP hp;
HeapInit(&hp);
// 创建一个K个数的小堆
for (int i = 0; i < k; ++i)
{
HeapPush(&hp, a[i]);
}
// 剩下的N-K个数跟堆顶的数据比较c;比他大c;就替换他进堆
for (int i = k; i < n; i++)
{
if (a[i] > HeaPTOP(&hp))
{
hp.a[0] = a[i];
AdjustDown(hp.a, hp.size, 0);
}
}
HeapPrint(&hp);
HeapDestroy(&hp);
}
觉得写的不错可以给个一键三连
点赞👍关注💡收藏💖@H_197_38@(咱就是说白嫖这行为不好)
以上是大佬教程为你收集整理的数据结构--TopK问题全部内容,希望文章能够帮你解决数据结构--TopK问题所遇到的程序开发问题。
如果觉得大佬教程网站内容还不错,欢迎将大佬教程推荐给程序员好友。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。