银川建网站,中国网站建设公司有哪些方面,建网站盈利,wordpress如何查看插件topK问题#xff1a; N个数找最大或者最小的前k个。 例子#xff1a; 优质筛选#xff08;店面的排名#xff09; 10000个数#xff0c;找出最大的前10个数 解决思路#xff1a;建立大堆#xff0c;然后pop9次 但是有些场景#xff0c;上面的思路…topK问题 N个数找最大或者最小的前k个。 例子 优质筛选店面的排名 10000个数找出最大的前10个数 解决思路建立大堆然后pop9次 但是有些场景上面的思路解决不了比如N非常大 比如N10亿k100 这里的空间就会不够 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.
