topK总结(初稿)
问题1 在n个有序数组中，求topK
假定有20个有序数组，每个数组有500个数字，降序排列，数字类型32位uint数值，现在需要取出这10000个数字中最大的500个
假如有n个数组升序， 每个数字长度是m 求这n个数组中(n*m) 最大的k个数
考察基础：两个有序数组合并
1.1 step 用最容易理解方式去做
两个数组两个数组比较
1 定义一个新的数组大小是TOP[k] 然后遍历n个数组 假如是第一个数组a[0]，将最大的k个数 赋值给top[k] 2 假如是第二个数组a[1]，将最大的k个数 和top[k] 进行比较 : 两个有序链表排序选出前k大 //伪代码 while(ib) {TOP[k]=a[n-i]} }
3 重复步骤2 直到遍历n个数组 TOP[k]记录就是结果
1.2优化
步骤2可用折半查找完成 gettopK
1.3分析：
时间复杂度：O(n^2) 数组两两比较获取结果 空间复杂度：O(m)
2 用最大堆堆排序：
竖向遍历 可参考基数排序 n有序链表合并成一个有序链表
- 两个有序数组 分别取出 1个记录 累计2个变量, 很容易判读那个是最大的
- n个数组，分别取出1个记录 累计n个变量，这有相当于有形成一个新的数组，要求是获取最大的一个。 heap排序 priority_queue具备这个特性
步骤 2.1 step:
- 建立大顶堆，维度为数组的个数，这里为20（第一次 插入的是每个数组中最大的值，即第一个元素）。
- 删除最大堆堆顶，保存到数组或者栈中，然后向最大堆插入删除的元素所在数组的下一个元素。
- 重复第1,2个步骤，直到删除个数为最大的K个数，这里为500.
2.2
时间复杂度：O(nlogn) 减少比较次数 n为外围循环 logn调整一次时间 空间复杂度：heap O(n)
2.3 对比
和归并排序对比 heap减少占用更少空间 只需要大小为n的数组 因为归并需要完全排序完毕才 只需要大小为n×m的数组
归并排序需要把待排数据全部存储内存中
问题2 海量数据处理的 Top K算法(问题)
问题描述： 有N(N>>10000)个整数,求出其中的前K个 最大的数。
最小堆 每次有数据输入的时候可以先与根节点比较
- 若不大于根节点，则舍弃
- 否则用新数值替换根节点数值, 并进行最小堆的调整
扩展思考:
假如要对一个很大记录的文件进行全部排序呢？ 回答： 利用B+思想 大文件拆分整体有序小文件
考点： 题目要求最大的k个数 不要求全部排序
问题3 一个无顺数组中求top K
问题 4 判读是否存在重复
A Bloom Filter is a probabilistic data structure that is used to test whether an element is a member of a set, or more simply,
instead of storing each value, a bloom filter is simply an array of bits indicating the presence of that key in the filter
参考
1 http://www.cnblogs.com/ywl925/p/3794852.html 2 http://blog.csdn.net/collonn/article/details/19039931
3 http://blog.csdn.net/gzxcyy/article/details/13510995 4 http://www.cnblogs.com/xudong-bupt/archive/2013/03/20/2971262.html 5 http://blog.csdn.net/v_july_v/article/details/7382693
7 https://en.wikipedia.org/wiki/Bloom_filter 8 instead of storing each value https://www.igvita.com/2008/12/27/scalable-datasets-bloom-filters-in-ruby/