企业官网建设流程全解析

• 文档
• 教程
• 知识库

导读

本篇整理自 InterviewGuide 仓库中阿秀总结的海量数据处理面试题系列（第 6–10 题），覆盖了互联网大厂面试中最高频的四类场景化问题：统计最热门的查询串（TopK）、统计不同电话号码的个数（判重）、从 5 亿个数中找出中位数、按 query 频度排序以及从多路有序数组找出前 500 大的数。读完本篇，你将掌握"内存装不下时"的通用解题三板斧——分而治之 + 哈希取余、HashMap 统计频数、大小顶堆求 TopN，并能把位图法、前缀树、双堆法与仓库内的 LeetCode 题解一一对应起来，做到面试手撕不慌。

本系列前 5 题（从大量 URL 中找相同、找高频词、找最多访问 IP、找不重复整数、判断数是否存在等）见同目录的 07-01-massive_data.md，本篇承接其解题思想继续深入。

一、如何查询最热门的查询串？

题目描述

搜索引擎会通过日志文件把用户每次检索使用的所有查询串都记录下来，每个查询串的长度不超过255 字节。

假设目前有1000w 个记录（这些查询串的重复度比较高，虽然总数是 1000w，但如果除去重复后，则不超过 300w 个）。请统计最热门的10 个查询串，要求使用的内存不能超过1G。（一个查询串的重复度越高，说明查询它的用户越多，也就越热门。）

内存估算：为什么不能一次性读入？

每个查询串最长为 255B，1000w 个串需要占用约2.55G内存：

1000w × 255B ≈ 2.55G > 1G

因此，我们无法将所有字符串全部读入到内存中处理。针对"数据总量大、去重后规模小、要求 TopN"这一类问题，有三种经典思路。

方法一：分治法

分治法依然是海量数据处理里非常实用的通用方法：

1. 把大文件划分为多个小文件，保证单个小文件中的字符串能被直接加载到内存中处理；
2. 求出每个文件中出现次数最多的 10 个字符串；
3. 最后通过一个小顶堆统计出所有文件中出现最多的 10 个字符串。

方法可行，但不是最好，下面两种方法在本题背景下更优。

方法二：HashMap 法

虽然字符串总数比较多，但去重后不超过 300w，因此可以考虑把所有字符串及出现次数保存在一个 HashMap 中：

300w × (255 + 4) ≈ 777M

其中 4 表示整数（出现次数）占用的 4 个字节。由此可见，1G 的内存空间完全够用。

思路如下：

• 第一步：遍历字符串，若不在 map 中，直接存入 map，value 记为 1；若在 map 中，则把对应的 value 加 1。这一步时间复杂度为O(N)；
• 第二步：遍历 map，构建一个10 个元素的小顶堆。若遍历到的字符串的出现次数大于堆顶字符串的出现次数，则进行替换，并将堆调整为小顶堆；
• 第三步：遍历结束后，堆中 10 个字符串就是出现次数最多的字符串。这一步时间复杂度为O(Nlog10)。

方法三：前缀树法

方法二使用了 HashMap 来统计次数，当这些字符串有大量相同前缀时，可以考虑使用**前缀树（Trie）**来统计字符串出现的次数，树的结点保存字符串出现次数，0 表示没有出现。

思路如下：

• 在遍历字符串时，在前缀树中查找：如果找到，则把结点中保存的字符串次数加 1；
• 否则为这个字符串构建新结点，构建完成后把叶子结点中字符串的出现次数置为 1；
• 最后依然使用小顶堆来对字符串的出现次数进行排序。

方法总结

前缀树经常被用来统计字符串的出现次数，它的另外一个大的用途是字符串查找、判断是否有重复的字符串等。当数据集中存在大量共享前缀时，前缀树相比 HashMap 还能进一步降低存储成本、提高查询效率（这一思路与本系列第 1 题"如何从大量 URL 中找出相同的 URL"中提到的字典树方案一脉相承，详见 07-01-massive_data.md）。

二、如何统计不同电话号码的个数？

题目描述

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

解答思路：位图法

这道题本质还是求解数据重复的问题，对于这类问题，一般首先考虑位图法（位图的基本原理与本系列第 4 题"在 2.5 亿个整数中找出不重复的整数"一致，可对照阅读 07-01-massive_data.md）。

对于本题，8 位电话号码可以表示的号码个数为10^8个，即1 亿个。我们每个号码用一个 bit 来表示，则总共需要 1 亿个 bit，内存占用约：

10^8 bit = 12.5MB ≈ 12M

思路如下：

1. 申请一个位图数组，长度为 1 亿，初始化为 0；
2. 遍历所有电话号码，把号码对应的位图中的位置置为 1；
3. 遍历完成后，如果 bit 为 1，则表示这个电话号码在文件中存在，否则不存在；
4. bit 值为 1 的数量即为不同电话号码的个数。

方法总结

求解数据重复问题，记得考虑位图法。位图以 bit 为存储单位，能把"一个整数是否出现/出现几次"的信息压缩到极致，非常适合判重、快速查找与排序类场景。本系列第 4、5 题（找不重复整数、判断一个数是否存在）也都是位图法的典型应用。

三、如何从 5 亿个数中找出中位数？

题目描述

从5 亿个数中找出中位数。数据排序后，位置在最中间的数就是中位数：

• 当样本数为奇数时，中位数为第(N+1)/2个数；
• 当样本数为偶数时，中位数为第N/2个数与第1+N/2个数的均值。

思路分析

如果这道题没有内存大小限制，则可以把所有数读到内存中排序后找出中位数。但是最好的排序算法的时间复杂度都为O(NlogN)，这里使用其他方法。

方法一：双堆法

维护两个堆：一个大顶堆、一个小顶堆。

• 大顶堆中最大的数小于等于小顶堆中最小的数；
• 保证这两个堆中的元素个数的差不超过 1。

判定规则：

• 若数据总数为偶数，当这两个堆建好之后，中位数就是这两个堆顶元素的平均值；
• 当数据总数为奇数时，根据两个堆的大小，中位数一定在数据多的堆的堆顶。

原文档给出了完整的 Java 实现（对应 LeetCode 第 295 题"数据流的中位数"）：

class MedianFinder { private PriorityQueue<Integer> maxHeap; private PriorityQueue<Integer> minHeap; /** initialize your data structure here. */ public MedianFinder() { maxHeap = new PriorityQueue<>(Comparator.reverseOrder()); minHeap = new PriorityQueue<>(Integer::compareTo); } public void addNum(int num) { if (maxHeap.isEmpty() || maxHeap.peek() > num) { maxHeap.offer(num); } else { minHeap.offer(num); } int size1 = maxHeap.size(); int size2 = minHeap.size(); if (size1 - size2 > 1) { minHeap.offer(maxHeap.poll()); } else if (size2 - size1 > 1) { maxHeap.offer(minHeap.poll()); } } public double findMedian() { int size1 = maxHeap.size(); int size2 = minHeap.size(); return size1 == size2 ? (maxHeap.peek() + minHeap.peek()) * 1.0 / 2 : (size1 > size2 ? maxHeap.peek() : minHeap.peek()); } }

该方法对应 LeetCode No.295 Find Median from Data Stream，可用于在线流式数据的动态中位数维护。

但要注意该方法的适用前提：以上这种方法需要把所有数据都加载到内存中。当数据量很大时，就不能这样了。5 亿个数，每个数字占用 4B，总共需要 2G 内存。如果可用内存不足 2G，就不能使用这种方法了，下面介绍另一种方法。

方法二：分治法

分治法的思想是把一个大的问题逐渐转换为规模较小的问题来求解。

对于这道题：

1. 顺序读取这 5 亿个数字，对于读取到的数字 num，如果它对应的二进制中最高位为 1，则把这个数字写到 f1 中，否则写入 f0 中；
2. 通过这一步，可以把这 5 亿个数划分为两部分，而且f0 中的数都大于 f1 中的数（最高位是符号位）；
3. 划分之后，可以非常容易地知道中位数是在 f0 还是 f1 中。假设 f1 中有 1 亿个数，那么中位数一定在 f0 中，且是在 f0 中从小到大排列的第 1.5 亿个数与它后面的一个数的平均值。

提示：5 亿个数的中位数是第 2.5 亿个与右边相邻一个数求平均值。若 f1 有一亿个数，那么中位数就是 f0 中从第 1.5 亿个数开始的两个数求得的平均值。

4. 对于 f0 可以用次高位的二进制继续将文件一分为二，如此划分下去，直到划分后的文件可以被加载到内存中，把数据加载到内存中以后直接排序，找出中位数。

注意：当数据总数为偶数，如果划分后两个文件中的数据有相同个数，那么中位数就是数据较小的文件中的最大值与数据较大的文件中的最小值的平均值。

方法总结

分治法把"内存放不下的大问题"逐步切割成"内存放得下的小问题"，每次切割只保留与中位数相关的一半数据，信息损失可控，非常适合超大文件求中位数、求分位数等场景。

四、如何按照 query 的频度排序？

题目描述

有10 个文件，每个文件大小为1G，每个文件的每一行存放的都是用户的 query，每个文件的 query 都可能重复。要求按照 query 的频度排序。

解答思路

如果 query 的重复度比较大，可以考虑一次性把所有 query 读入内存中处理；如果 query 的重复率不高，那么可用内存不足以容纳所有的 query，这时候就需要采用分治法或其他方法来解决。

方法一：HashMap 法

如果 query 重复率高，说明不同 query 总数比较小，可以考虑把所有的 query 都加载到内存中的 HashMap 中。接着就可以按照 query 出现的次数进行排序。

方法二：分治法（哈希取余 + 外排序）

分治法需要根据数据量大小以及可用内存的大小来确定问题划分的规模。对于这道题：

1. 顺序遍历 10 个文件中的 query，通过 Hash 函数hash(query) % 10把这些 query 划分到 10 个小文件中；
2. 之后对每个小文件使用 HashMap 统计 query 出现次数，根据次数排序并写入到另外一个单独文件中；
3. 接着对所有文件按照 query 的次数进行排序，这里可以使用归并排序（由于无法把所有 query 都读入内存，因此需要使用外排序）。

方法总结

• 内存若够，直接读入进行排序；
• 内存不够，先划分为小文件，小文件排好序后，整理使用外排序进行归并。

五、如何找出排名前 500 的数？

题目描述

有20 个数组，每个数组有500 个元素，并且有序排列。如何在这20 × 500个数中找出前 500的数？

解答思路：堆排序

对于 TopK 问题，最常用的方法是使用堆排序。对本题而言，假设数组降序排列，可以采用以下方法：

1. 首先建立大顶堆，堆的大小为数组的个数，即为20，把每个数组最大的值存到堆中；
2. 接着删除堆顶元素，保存到另一个大小为 500 的数组中，然后向大顶堆插入删除的元素所在数组的下一个元素；
3. 重复上面的步骤，直到删除完第 500 个元素，也即找出了最大的前 500 个数。

为了在堆中取出一个数据后，能知道它是从哪个数组中取出的，从而可以从这个数组中取下一个值，可以把数组的指针存放到堆中，对这个指针提供比较大小的方法。

原文档给出的完整 Java 实现如下（核心是DataWithSource记录"数值 + 来源数组 + 数组内索引"，并通过改写compareTo让默认小顶堆的PriorityQueue变成大顶堆）：

import lombok.Data; import java.util.Arrays; import java.util.PriorityQueue; public class DataWithSource implements Comparable<DataWithSource> { /** * 数值 */ private int value; /** * 记录数值来源的数组 */ private int source; /** * 记录数值在数组中的索引 */ private int index; public DataWithSource(int value, int source, int index) { this.value = value; this.source = source; this.index = index; } /** * * 由于 PriorityQueue 使用小顶堆来实现，这里通过修改 * 两个整数的比较逻辑来让 PriorityQueue 变成大顶堆 */ @Override public int compareTo(DataWithSource o) { return Integer.compare(o.getValue(), this.value); } } class Test { public static int[] getTop(int[][] data) { int rowSize = data.length; int columnSize = data[0].length; // 创建一个columnSize大小的数组，存放结果 int[] result = new int[columnSize]; PriorityQueue<DataWithSource> maxHeap = new PriorityQueue<>(); for (int i = 0; i < rowSize; ++i) { // 将每个数组的最大一个元素放入堆中 DataWithSource d = new DataWithSource(data[i][0], i, 0); maxHeap.add(d); } int num = 0; while (num < columnSize) { // 删除堆顶元素 DataWithSource d = maxHeap.poll(); result[num++] = d.getValue(); if (num >= columnSize) { break; } d.setValue(data[d.getSource()][d.getIndex() + 1]); d.setIndex(d.getIndex() + 1); maxHeap.add(d); } return result; } public static void main(String[] args) { int[][] data = { {29, 17, 14, 2, 1}, {19, 17, 16, 15, 6}, {30, 25, 20, 14, 5}, }; int[] top = getTop(data); System.out.println(Arrays.toString(top)); // [30, 29, 25, 20, 19] } }

从示例main可以看到：3 个降序数组{29,17,14,2,1}、{19,17,16,15,6}、{30,25,20,14,5}运行后输出[30, 29, 25, 20, 19]，即正确取出了前 5 大的数。该思路本质上是"多路归并 + 堆"：堆中始终只保留每个数组当前的最大候选值（堆大小 = 数组个数），每次弹出全局最大后从同源数组补位，从而把时间复杂度控制在O(Nlogk)量级（N 为总元素数，k 为数组个数）。

六、源码佐证：堆与 TopK 在 InterviewGuide 算法题库中的落地

本篇五道题反复用到两个底层数据结构——堆（小顶堆/大顶堆）与位图/哈希。InterviewGuide 的算法题库为它们提供了大量可直接刷的配套题解：

1. 堆排序基础实现

02-07-十大排序.md 给出了堆排序的 C++ 实现，包含三个核心函数：

• heapify：对第 i 个结点取根、左、右的最大值并下沉调整（建堆与调整的基础操作）；
• heapify_build：从树的倒数第二层第一个结点开始，自底向上建大根堆；
• heapify_sort：建好大根堆后，每次交换最后一个结点和根节点（最大值），再对交换后的根节点继续heapify（此时堆的最后一位已是最大值，n 变为 n-1）。

这与本篇第 5 题"先建堆、反复取堆顶"的思路完全一致，先掌握裸堆排序，再理解多路堆归并会容易很多。另外在 02-algorithm-basic.md 中，堆排序被列为非稳定排序，时间复杂度O(nlogn)，这是面试中常被追问的知识点。

2. "求前 k 大用最小堆"的口诀在 LeetCode 题解中的印证

347.前K个高频元素.md 中有一句醒目的提示，与本篇第 1、2、5 题的方法论完全同源：

求前 k 大，用小根堆；求前 k 小，用大根堆。面试的时候如果说反了会挂！

其题解正是"unordered_map统计频数 +priority_queue维护大小为 k 的小根堆，堆满后弹出堆顶"，与本题"HashMap 统计 + 10 元素小顶堆"的流程一一对应：

priority_queue<pair<int, int>, vector<pair<int, int>>, compare> freq; for (auto &a : hash) { freq.push(a); if (freq.size() > k) freq.pop(); }

类似的还有：

• 215.数组中的第K个最大元素.md：用大小为 k 的小顶堆priority_queue<int, vector<int>, greater<int>>一趟求出第 k 大元素，是 TopK 问题最直接的落地；
• 692.前K个高频单词.md：在频数相同的情况下再按字典序比较，展示了如何通过自定义比较器扩展堆的排序规则（本题DataWithSource的compareTo正是同一技巧）。

3. 分治 + 哈希取余的通用套路

本篇第 1、4 题使用的"hash(x) % N拆小文件"套路，与本系列第 1、2、3 题（07-01-massive_data.md）中的"分而治之，进行哈希取余"完全一致，是海量数据处理面试题出现频率最高的通用解法，建议作为第一反应优先考虑。

七、五题方法论总览

面试记忆要点：

1. 数据总量大、内存装不下 →分而治之，哈希取余拆小文件；
2. 拆完后统计频数 →HashMap / 前缀树；
3. 求最大的 TopN 用小顶堆，求最小的 TopN 用大顶堆；
4. 判重、判断存在 →位图法；
5. 多路有序数据取前 N →大小为路数的大顶堆 + 同源补位（多路归并）；
6. 大文件整体排序 →小文件各自排好后用外排序归并。

掌握以上六条，再配合仓库算法题库中的 堆排序实现、347 前 K 个高频元素、215 第 K 个最大元素 与 692 前 K 个高频单词 反复练习，海量数据处理这一类"场景题"基本可以做到举一反三、稳定拿下。

• 文档
• 教程
• 知识库