面试真题：经典海量数据处理题最详解析（下）

前言

大家好，我是鬼仔，今天接着和大家聊聊海量数据处理题的解题思路。

前情概要：在上篇中，问题原形是在海量数据中找出重复次数最多的一个/前N个数据，我们的解决方法是：分而治之/Hash映射 + HashMap/前缀树统计频率 + 堆/快速/归并排序。具体可见：面试真题：经典海量数据处理题最详解析（上）。

今天给大家介绍下海量数据处理题的另一种常见题型：在海量数据中找出第k大/中位数/不重复或重复的数字，解决方法关键还是在于分治，通过多次划分，逐步确定范围，然后最后在一个可以接受的范围内处理数据。一句话：分就完事了！不过今天七夕好像不太方便这么说...

除此之外，鬼仔还会给大家介绍一种大数据场景中常用的算法：位图法（BitMap）。话不多说，咱们马上进入实战！

公众号：码农鬼仔，专注分享算法知识｜面试技巧｜职场感悟｜内推信息。

一、2.5亿个整数中找出不重复的整数的个数，内存空间不足以容纳这2.5亿个整数。

整数int有4个byte，所有整数个数有2^32，这里可以继续使用分而治之、hash映射的方法，即对于每个整数x，取hash(x)并模N，N代表划分的小文件个数，这样相同的整数会存入同一个文件，接着通过HashMap统计每个小文件中整数出现的频率（key为整数，value为频率），最后value为1的整数即为所求。

除此之外，我们还可以使用一种特殊的数据结构：位图（BitMap）。

位图的思想是用bit数组来记录0-1两种状态，可以将具体数据映射到这个bit数组的对应位置，bit数组中0表示数据存在，1表示数据不存在。举个例子，利用位图表示0-5中的元素，0-5中只有6个数，所以用6bit足以表示，例如3可以表示为[0,0,0,1,0,0]。位图在大量数据查询、去重等应用场景中使用的比较多，这个算法具有比较高的空间利用率。

回到该题，要找出不重复的整数，那么一个整数可以有三种状态，即不存在、存在1次、存在多次，根据题目需要找出的是存在1次的整数。对于三种状态只用0或1肯定是表示不了的，采用2-Bitmap（每个数分配2bit，00表示不存在，01表示出现一次，10表示多次，11无意义）。具体做法为：首先遍历所有整数，查看对应位图中对应的位，如果是 00，则变为 01，如果是 01 则变为 10，如果是 10 则保持不变。最后遍历位图，找出01对应的整数，即为2.5亿整数中只出现一次的整数。

我们也可以采用两个BitMap，即第一个Bitmap存储的是整数是否出现，接着，在之后的遍历先判断第一个BitMap里面是否出现过，如果出现就设置第二个BitMap对应的位置也为1，最后遍历BitMap，仅仅在一个BitMap中出现过的元素，就是不重复的整数。

二、已知某个文件内包含一些电话号码，每个号码为 8 位数字，统计不同号码的个数。

这类题目使用位图法最为简单，每个号码八位数，不考虑实际情况，8位最多99 999 999，一共有10^8种情况，也就是需要10^8位bit，大概12.5M内存即可。申请一个数组，遍历所有号码，将号码对应的bit置为1，最后统计bit位1的数量即为不同的号码数。

三、5亿个int整数找它们的中位数

我们先明确中位数的定义：中位数是按顺序排列的一组数据中居于中间位置的数，即在这组数据中，有一半的数据比他大，有一半的数据比他小，如果这组数据有偶数个，那么取中间的两个数值的平均数作为中位数。

解法一：当内存不足以存放5亿个int整数时，我们依然使用分而治之的方法，但hash映射分成小文件的时候需要注意，我们要保证把数据分散到不同文件中时仍然保持着顺序，即按数值大小进行分流，这样才能找到正确的中位数。

我们遍历这5亿个int整数时，考虑其二进制的最高位，按照最高位（符号位，0表示正数，1表示负数）进行二分，即最高位为1存入文件a，最高位为0存入文件b，这样文件a中的数是一定比文件b中的数小。
统计文件a和文件b中的整数个数，如果文件a和文件b中的整数个数相同，那么中位数则是文件a中的最小值和文件b中的最大值的平均值。如果文件a中的整数个数小于文件b，那么中位数肯定在文件b中，反之亦然。
如果文件a或文件b中的整数还是无法直接读取进内存中，那么继续使用上个步骤的方法进行分流，并判断中位数所处的位置，直到中位数所在的那部分数据大小可以直接放到内存中，然后对这部分排序，计算出中位数的值。

解法二：空间换时间，巧妙利用大小堆。这其实可以用力扣295题（数据流的中位数）的方法进行解答，我摘抄下高赞的解法给同学们参考下：

题目：

解答：

代码（Java）：

class MedianFinder {
    PriorityQueue<Integer> l = new PriorityQueue<>((a,b)->b-a);
    PriorityQueue<Integer> r = new PriorityQueue<>((a,b)->a-b);

    public void addNum(int num) {
        int s1 = l.size(), s2 = r.size();
        if (s1 == s2) {
            if (r.isEmpty() || num <= r.peek()) {
                l.add(num);
            } else {
                l.add(r.poll());
                r.add(num);
            }
        } else {
            if (l.peek() <= num) {
                r.add(num);
            } else {
                r.add(l.poll());
                l.add(num);
            }
        }
    }

    public double findMedian() {
        int s1 = l.size(), s2 = r.size();
        if (s1 == s2) {
            return (l.peek() + r.peek()) / 2.0;
        } else {
            return l.peek();
        }
    }
}