假定有20个有序数组,每个数组有500个数字,降序排列,数字类型32位uint数值,现在需要取出这10000个数字中最大的500个
假如有n个数组升序, 每个数字长度是m 求这n个数组中(n*m) 最大的k个数
考察基础:两个有序数组合并
两个数组两个数组比较
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]记录就是结果
步骤2可用折半查找完成 gettopK
时间复杂度:O(n^2) 数组两两比较获取结果 空间复杂度:O(m)
竖向遍历 可参考基数排序 n有序链表合并成一个有序链表
步骤 2.1 step:
2.2
时间复杂度:O(nlogn) 减少比较次数 n为外围循环 logn调整一次时间 空间复杂度:heap O(n)
2.3 对比
和归并排序对比 heap减少占用更少空间 只需要大小为n的数组 因为归并需要完全排序完毕才 只需要大小为n×m的数组
归并排序需要把待排数据全部存储内存中
问题描述: 有N(N>>10000)个整数,求出其中的前K个 最大的数。
最小堆 每次有数据输入的时候可以先与根节点比较
假如要对一个很大记录的文件进行全部排序呢? 回答: 利用B+思想 大文件拆分整体有序小文件
考点: 题目要求最大的k个数 不要求全部排序
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/