海量数据中的TOPK问题小结

时间:2023-01-19 00:38:57

1.利用堆找出最大的K个数

  首先,先理解下用堆找出最大的K个数的常用解法,例如问题是“从M(M <= 10000)个数中找出最大的K个数”

(1)利用最大堆

  建立一个N=M大小的大顶堆,然后输出根节点之后,将根节点删除,然后再将剩余的元素调整成大顶堆;依次重复K次这个过程,最终就找出了K个最大的数。这实质上就是堆排序的过程。这种方法的时间复杂度为O(K *logM)

(2)利用最小堆

  这是最常用的一种方式,首先建立一个N=K大小的小顶堆,这K个元素可以为M中元素中的任意K个;我们假设这K个元素就是最大的K个元素(其中根节点是这K个元素中最小的元素);那么对于剩下的M-K个元素,我们逐个与根节点进行对比,

如果当前元素大于根节点的元素的话,就将当前的元素与根节点的元素进行交换,然后将堆再次进行进行调整成最小堆,重复这个过程,直到比较完剩下的M-K个元素;那么最终的小顶堆对应的K个数,必然是M个数中的最大的K个数。这种方法的

时间复杂度为O(M*logK);并且方法2相对方法1而言,所需要的内存空间更小了,方法1建立的堆需要M个元素对应的内存空间,而方法2建立的堆只需要K个元素对应的内存空间,所以在对内存空间有严格要求的情况下,采用方法2会更加好一些。

2.海量数据中找出最大的K个数

  对于1而言,M这个指不能很大;如果M很大的话(比如M = 40亿),就不能直接使用排序来找了。对于这种情况,一般是利用“hash映射+堆”的过程,这里的堆是指的方法2,具体如下:

将40亿个数分成若干小的部分(分成多少部分要看题目对内从空间大小的限制),一般是利用哈希函数$h(x) = x% N$,其中N为分成的部分数;然后对于每个小的部分,如果内存可以一次性读取的话,则利用堆采用方法2,选取每个小部分数据中的TOPK个元素,一共

N*K个元素,然后继续利用堆,采用方法2从这N*K个元素种找出最大的K个元素。

3.找出100亿个URL中重复的URL

  (1)对于这类问题,通常采用的的算法思想是“hash映射+哈希表”;大体而言,将100亿个URL利用哈希函数分成N个部分,每个部分用哈希表进行统计次数,最终找到所有重复的URL。

  (2)利用字典树。

4.找出20亿个数中出现次数最多的数

  解决这类问题的想和3中的法(1)类似。

5.找出40亿个非负整数中出现0次、1次...N次的数

  一般找出非负整数中的出现多少次的数,都是利用BItMap

此处只是粗略的总结下,更详细的总结可参考左神的《程序员代码面试指南--IT名企算法与数据结构题目最优解》和July的https://blog.csdn.net/v_july_v/article/details/7382693