big-data

一个很容易的问题

如果想在一个数组中找到前3个最小值。最基础的做法就是构建小根堆，构建完弹出3个元素就行了。

注意：上述这种方法对堆的大小没有限制，如果有限制呢？想要求top K最小值，那么就构建一个大根堆。当堆中的元素小于容量时，入堆就行。如果堆满了，有新来的数，那么只要看准备进来的值和堆顶谁大。如果比堆顶还大，说明准备进来的值肯定不是数组的top K小的值。自然不用考虑。判断下一个元素即可。(容量满时，只有比堆中元素小时，才能进堆,所以进来的都是比原来小的)。 当处理完所有元素，堆中就是前k小的元素。

求相应的前k大值是类似的。

那么如果要求第二组top k的元素呢？ 只需要在处理元素时，判断当前元素与上一组元素的最大值，比上一组最大值大的元素才是我们希望处理的元素。(因为重新遍历文件仍会遇到我们以前处理过的元素)

大数据相关题目

区间统计思想

32位无符号整数的范围是0~4294967295，现在有40亿个无符号整数，可以使用最多1GB的 内存，找出所有出现了两次的数。如果可以使用最多10MB的内存，怎么找到这40亿个整数的中位数？

40亿个数，32位int能够表示的范围 $0$~$2^{32} - 1$;所以int32能够表示的范围肯定不止40亿个。个数为$2^{32}$个。

假设只能用10KB内存，首先可以看看10KB能申请多少个无符号整数。然后找到离个数最近的2的整数次幂。$10KB/4B\approx2500$个，所以最近的2的整数次幂就为$2^{11}=2048$个。

所以就可以申请一个长度为2048的无符号整型数组。 数组中的每一个元素表示一个范围。对$2^{32}$划分成2048份，每一份表示一个数据范围。然后遍历文件，统计每个范围内数的出现个数。那么不断叠加出现次数。就可以找到词频刚好大于等于20亿个那个范围。

然后再对刚才所找到的范围继续划分，在对继续划分的范围内找到位置为2亿的那个数。如此反复，就可以找到中位数了。

范围统计就差不多这么个意思。分段统计大文件的信息。

堆

大数据相关的题目，有时需要使用堆来保持一个局部的大小关系。