历史题目复盘：10G 个整数只有 2G 内存，中位数怎么找

深蓝黑背景品牌封面：居中大标题两行「10G 个整数只有 2G 内存，中位数怎么找」，副标题「分桶计数：两遍扫描定位中位」；下方装饰——一排高矮不一的分桶柱条，横轴中央一根青色基准线标注「中位数落在哪一桶，由累计计数说了算」，其中一个桶被青色高亮；顶部标注「历史题目复盘 · 数据处理」与「Day 10 · 09-28」图 1：本文封面，点明「两遍扫描定位中位」的主线。

先说明属性：这是一篇历史题目复盘，题目出自本地历史面试资料（见文末来源说明），与任何公司的当前招聘无关。「内存装不下，还要算中位数」是海量数据处理的经典题型，面试官想考察的不是排序算法，而是你能否把「排序整个数据集」换成「计数加定位」。

先给核心结论：分桶计数三遍走——第一遍流式扫描只给桶计数，内存里只有几百个计数器；按计数累加定位中位数所在的桶；第二遍扫描只把中位桶的数读进内存，排序取中位。总代价是两遍磁盘扫描，任意时刻内存只装一个桶。2G 内存绰绰有余。

第一步，先算清楚约束。

10G 个整数，按每个 8 字节算是 80G 数据，2G 内存连零头都装不下，任何「全部读进来再说」的思路直接出局。但换一个角度：中位数是第 50 亿小的那个数，要回答「它是谁」，未必需要知道所有数的名次——只需要知道「比它小的有多少个」。计数比排序便宜得多，这就是破题口。

第二步，分桶计数的三步。

第一遍，分桶计数。按数值高位把整数划进若干桶，比如 64 位整数按高 8 位分 256 个桶。流式扫一遍文件，每个数只让对应桶的计数器加一。内存里只有 256 个计数器，按 8 字节一个总共 2KB，毫无压力。

第二遍，定位中位桶。从最小的桶开始累加计数，加到总数一半的那一刻，所在的桶就是中位数所在的桶——它之前的桶装不下前 50 亿个，它之后装得超。

第三遍，桶内精读。只把这个桶的数重新从磁盘扫进内存。一个桶大约装总数量的二百五十六分之一，约 4000 万个数，300 多 MB，2G 内存轻松装下。排序后按偏移取出中位数。如果某个桶还是太大，就在桶内再按次高位细分一层，递归下去直到装得下。

流程图：①分桶计数——按数值高位把 10G 个整数划进 256 个桶，流式扫描一遍只给桶计数，计数器总共不到 2KB，内存毫无压力；②定位中位桶——从最小桶开始累加计数，加到超过总数一半的那一刻，所在桶就是中位数所在的桶；③桶内精读——只把这一个桶的数重新扫进内存，排序或继续细分，取出中位数。下方说明：总代价是两遍磁盘扫描，任意时刻内存只装一个桶；备选方案是外部排序——归并排序后取中间位置，思路正确但要多轮读写，分桶更省。底部结论：内存装不下不等于算不了，把「排序整个数据集」换成「计数加定位」即可图 2：分桶找中位数的三步流程，以及与外部排序的代价对比。

第三步，用小数据验证一遍思路。

下面这段代码把「256 个高位桶」缩小成「按十位数分 10 个桶」，完整演示三遍流程并用全排序交叉复核，用 Node.js 22.15.0 直接运行（node median.js）：

'use strict';

// 分桶找中位数：第一遍只计数，第二遍只精读中位桶
// 这里用小整数模拟：把「256 个高位桶」缩小成「按十位数分 10 个桶」
function bucketMedian(nums) {
  const buckets = new Array(10).fill(0);
  for (const n of nums) buckets[Math.floor(n / 10)]++; // 第一遍：流式计数，内存只有 10 个计数器

  const total = nums.length;
  const half = Math.floor((total + 1) / 2); // 中位数是第 half 小的数
  let acc = 0;
  let mid = -1;
  for (let b = 0; b < 10; b++) {
    if (acc + buckets[b] >= half) { mid = b; break; } // 累计计数跨过一半，中位数就在这个桶
    acc += buckets[b];
  }

  // 第二遍：只把中位桶的数装进内存排序，取出中位数
  const inBucket = nums.filter((n) => Math.floor(n / 10) === mid).sort((a, b) => a - b);
  return { bucket: mid, median: inBucket[half - acc - 1] };
}

// 全量排序复核（内存装得下时才能这么干）
function sortMedian(nums) {
  const sorted = [...nums].sort((a, b) => a - b);
  return sorted[Math.floor((sorted.length - 1) / 2)];
}

const cases = [
  [7, 3, 42, 15, 28, 91, 56, 33, 68, 24, 81],
  [5, 5, 5, 5, 5],
  [99, 1, 50, 50, 50, 2, 98],
  Array.from({ length: 1001 }, (_, i) => (i * 37) % 100), // 1001 个伪随机两位数
];
for (const nums of cases) {
  const { bucket, median } = bucketMedian(nums);
  const check = sortMedian(nums);
  console.log(`n=${nums.length} 中位桶=[${bucket * 10},${bucket * 10 + 9}] 分桶结果 ${median}，全排序复核 ${check}`);
  if (median !== check) throw new Error('两种方法结果不一致');
}

实测输出：

n=11 中位桶=[30,39] 分桶结果 33，全排序复核 33
n=5 中位桶=[0,9] 分桶结果 5，全排序复核 5
n=7 中位桶=[50,59] 分桶结果 50，全排序复核 50
n=1001 中位桶=[40,49] 分桶结果 49，全排序复核 49

四个用例两种方法全部一致，覆盖了全相同值、大量重复值、千级随机数据三个边界。

易错点清单。

一，第一反应是外部归并排序——思路正确但要多轮磁盘读写，讲不出分桶这个更省的方案就落了俗套。二，桶按个数平均分而不是按数值范围分——分桶的意义是让「第几小」能用计数定位，乱分就失去意义。三，忘记中位桶可能仍然装不下，要讲出递归细分的兜底。四，偶数个数据时中位数是两个中间值的平均，口径要先和面试官对齐，本文演示按奇数个处理。五，把 10G 个整数当成 10G 字节——数量与字节的换算是最先该算的账。

回到面试现场，建议的答题节奏：先算数据量与内存的账，排除全量加载；再给分桶计数三步，强调两遍扫描与内存占用；然后交代桶内过大的递归细分；最后补偶数口径与外部排序备选。数据集的中位数、分位数统计是特征工程的常规操作，内存受限下的分治统计，是数据工程师的基本功。

如果面试官把题目改成「数据是流式到来的，没有文件可以扫两遍」，分桶计数还成立吗？你会换什么近似算法？欢迎写出你的思路。

参考资料

Node.js v22.x 官方 API 文档（文中代码运行环境为 Node.js 22.15.0，Array.prototype.filter、数值下划线分隔符等行为以此为准） — https://nodejs.org/docs/latest-v22.x/api/

历史题目复盘：10G 个整数只有 2G 内存，中位数怎么找

参考资料

相关阅读