如何修改网站底部,软件工程导论,微信公众号微网站 建设报价表,wordpress 无法保存题目 有10亿个数字#xff0c;需要找出其中的前k大个数字。 为了方便讲解#xff0c;这里令k为5。
思路分析#xff08;以找前k大个数字为例#xff09;
很容易想到#xff0c;进行排序#xff0c;然后取前k个数字即可。 但是#xff0c;难点在于#xff0c;10亿个数…题目 有10亿个数字需要找出其中的前k大个数字。 为了方便讲解这里令k为5。
思路分析以找前k大个数字为例
很容易想到进行排序然后取前k个数字即可。 但是难点在于10亿个数字假设每个数字都是int就需要40亿个字节接近40G的内存这是很恐怖的数据肯定不可能直接进行排序。
那我们怎么办呢 我们可以建一个k个元素的堆 找前k大的数字建小堆找前k小的数字建大堆 接着将剩下N - k个数字与堆顶元素比较 如果比堆顶元素大就进入堆向下调整维护好堆 遍历完所有的数字即可 最终堆里面的元素就是前k大个数字 思路虽然不好想但是理解起来还是比较简单的 难点在于为什么找前k个大数字要建小堆呢
OK我们先假设建大堆。 当中途找到了最大的数字这个数字就会一直再堆顶如果后面还有其他前k大的数字但小于最大的数字就会被挡住无法进入堆。
所以找前k大个数字要建小堆找前k小个数字要建大堆是相同的道理。
时间复杂度分析
如果采用排序来寻找前K大个数字时间复杂度是O(N * logN) 但是采用建堆的思路时间复杂度是O(K (N - K) *logK) 因为N是远大于K的所以时间复杂度为O(N)优于排序算法。 而且空间复杂度也非常小。
整体思路上完全优于排序算法。
代码
10亿个数据太难造了这里就简单使用10万个数据模拟一下吧 用随机数模拟出10万个数据接着进行打桩在这10万个数据中造出一些特殊数据这里为1000001,1000002,1000003,1000004,1000005
void CreateNDate()
{// 造数据int n 100000;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;if (i 333)x 1000001;if (i 444)x 1000002;if (i 555)x 1000003;if (i 666)x 1000004;if (i 777)x 1000005;fprintf(fin, %d\n, x);}fclose(fin);
}void TopK(int k)
{const char* file data.txt;FILE* fout fopen(file, r);if (fout NULL){perror(fopen error);return;}int* heap new int[k];for (int i 0; i k; i){fscanf(fout, %d, heap[i]);}for (int i (k - 1 - 1) / 2; i 0; --i){AdjustDown(heap, k, i);}int x 0;while (fscanf(fout, %d, x) ! EOF){if (x heap[0]){heap[0] x;AdjustDown(heap, k, 0);}}for (int i 0; i k; i){cout heap[i] ;}cout endl;
}int main()
{CreateNData();TopK(5);return 0;
}
