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

TopK问题

news 2025/8/6 0:59:28

topK问题：

N个数找最大或者最小的前k个。
例子：
优质筛选（店面的排名）
   10000个数，找出最大的前10个数
   解决思路：建立大堆，然后pop9次


但是有些场景，上面的思路解决不了，比如N非常大
比如：N=10亿，k=100
这里的空间就会不够：
10亿个整数，需要多少空间——》1024*1024*1024byte ——》 4G
数据多时，内存不够，则会存入磁盘文件中（磁盘中的数据不可以随机访问，所以不可以建堆）

终极解决思路：

建立k个数的小堆
后面N-K个数有，一次比较，如果比堆顶的数据大，就替换他进堆
不断替换堆顶值，然后向下调整
最后，这个小堆的值就是最大的前k个数

void CreatNDate(){ int n = 1000;srand(time(0));const char * file = "data.txt";FILE *fin = fopen(file,"w");if(fin == NULL){perror("fopen error");return;}for (size_t i = 0; i < n; ++i){int x = rand()%1000000;fprintf(fin,"%d\n",x);} }void PrintTopK(int k){const char* file = "data.txt";FILE* fout = fopen(file, "r");if (fout == NULL){perror("fopen error");return;}int* kminheap = (int *)malloc(sizeof(int) * k);if (kminheap == NULL){perror("malloc error");return;}for (int i = 0; i < k; i++){fscanf(fout, "%d", &kminheap[i]);}//取前k个数，建立小堆for (int i = (k-1-1)/2; i >= 0; i--){AdjustDown(kminheap,k,i);}//读取剩下的数，谁比堆顶元素大，谁踢出堆顶元素然后进入这个堆。int val = 0;while (!feof(fout)){fscanf(fout, "%d", &val);if (val > kminheap[0]){kminheap[0] = val;AdjustDown(kminheap, k, 0);}}for (int i = 0; i < k; i++){printf("%d\n", kminheap[i]);}}

总结：

此方法的时间复杂度为：k+(n-k)*logk.

查看全文

http://www.lryc.cn/news/108860.html