大数据量题目

10亿数据找到前100大的数（Top K问题）

10亿数据，假设单个float32位的浮点数占4个字节，10亿浮点数就需要占用4G内存

直接排序

• 时间复杂度：使用快速排序对数据排序时复杂度为O(nlogn)

缺点：

1. 占用内存大
2. 浪费性能：目的是求出最大的100数，对所有数字排序显然很多是无用功

堆排序

先拿前一百个数建一个堆，一个小顶堆，然后依次遍历剩下的元素，跟堆顶比较，大于堆顶就替换堆顶，然后继续调整堆

建堆的时间复杂度m * logm（m是堆中元素个数），总时间复杂度: n * mlogm（n是总元素个数）

分治法（即大数据里最常用的MapReduce）

将数据分散成多份，通过多台机器分布式运算或者多线程并发计算的方式取得每份数据的Top K，然后汇总结果。

1. 将10亿个数据分为100份，每份1000w个数据（40MB）

2. 每份求出了top 100, 则继续在100 * 100个数据中求出 top 100

从2.5亿个数字里面找出不重复的数字的个数

2.5亿个整数（一个整数4B）一共需要1G的内存；int[]的Set结构需要1G内存

位图法

一个数可以用2bit来表示出现的情况：用00表示这个数字没有出现过，01表示出现过一次，10表示出现过多次，11暂不使用。

那么一个字节1B=8bit，则可以表示4个数字的状态

byte[] 数组需要1G/4的大小，即本来是1G直接减少4倍

分治法

把这2.5亿个数划分到更小的文件中，从而保证每个文件的大小不超过可用内存的大小。然后对于每个小文件而言，所有的数据可以一次性被加载到内存中，因此可以使用字典或set来找到每个小文件中不重复的数。当处理完所有的文件后就可以找出这2.5亿个整数中所有的不重复的数。