FindMedian大数据中位数难题airbnb题库堆分治方案的实战拆解【免费下载链接】airbnb项目地址: https://gitcode.com/gh_mirrors/ai/airbnb在 airbnb 面试题库AirBnB Interview Questions中第 8 题从海量整数文件中找中位数是大数据处理类的高频考题文件只能顺序读取、数据量超出内存容量要求你在线求中位数。本文用双堆与分治值域二分两条路线拆解这道大数据中位数难题带你读懂题库中 FindMedianinLargeIntegerFileofIntegers.java 的官方解法。 想动手练习仓库地址https://gitcode.com/gh_mirrors/ai/airbnb克隆后即可查看全部 30 道 Java 题解。一、题目拆解大数据中位数难在哪题目原文见 README.md 第 83 行Find the median from a large file of integers. You can not access the numbers by index, can only access it sequentially. And the numbers cannot fit in memory.三个限制条件直接决定了全量读入再排序是行不通的限制条件后果数据量超出内存不能一次性读入必须流式处理只能顺序访问不能随机跳转、不能直接排序后取中间中位数需要全局顺序单遍扫描无法直接得到需要维护状态或反复统计这正是海量整数文件中位数问题的本质用 O(1)~O(n) 的内存换出 O(1) 的查询结果。二、方案一双堆法流式在线中位数️ 思路维护两个堆实时跟踪已读数据的中位数。小顶堆 small存放较小的一半数据堆顶是这半部分的最大值大顶堆 large存放较大的一半数据堆顶是这半部分的最小值每读入一个数先塞进 small 再弹出堆顶放进 large保证 small 堆顶 ≤ large 堆顶再通过移动堆顶元素维持两堆大小相差不超过 1全部读完偶数个元素中位数 两堆堆顶平均值奇数个则取较大的那一堆的堆顶✅ 优点一遍读完即可出结果适合数据流持续到达、需要实时中位数的场景如实时监控指标。 ⚠️ 代价要缓存大约 n/2 个元素内存占用是 O(n)——对于文件大到根本放不下的场景偏大。三、方案二分治法值域二分题库官方实现题库给出的解法走的是另一条更省内存的路线对取值范围做二分查找。核心代码在src/main/java/find_median_in_large_file_of_integers/FindMedianinLargeIntegerFileofIntegers.java中。1. 分治思路把第 k 小变成计数问题不排数据而是猜一个值guess扫一遍文件统计≤ guess的个数countcount k→guess附近就是第 k 小count k→ 答案更大往右半区间继续分治count k→ 答案更小往左半区间继续分治每轮二分把搜索区间砍半所以总共只需O(log V) 遍扫描V 为数值范围int 范围即 32 次左右且内存只需 O(1)。2. 关键代码逐段解读核心递归函数search(nums, k, left, right)第 13–35 行long guess left (right - left) / 2; int count 0; for (int num : nums) { if (num guess) { count; res Math.max(res, num); // res≤ guess 的最大值 } } if (count k) { return res; } else if (count k) { return search(nums, k, Math.max(res 1, guess), right); } else { return search(nums, k, left, res); }三个细节值得新手注意res的妙用统计时顺手记录小于等于 guess 的最大实际值。这样返回的是文件里真实存在的数而不是二分猜出来的中间值同时它让下一步二分的边界可以跳过大段无用区间Math.max(res 1, guess)收敛更快。递归分治count k时答案必在(guess, right]count k时在[left, res]每次区间至少减半保证 O(log V) 轮。基线条件left right时区间收缩到一点直接返回。3. 入口函数奇偶长度分流findMedian(nums)第 37–49 行的处理逻辑先顺序遍历一遍统计总数len这一步是必须的——顺序访问下你并不天然知道文件里有多少个数奇数中位数 第len/2 1小的数调用一次search偶数中位数 第len/2小 与 第len/2 1小 的平均值调用两次search对应的单元测试第 52–60 行覆盖了三种情况奇数、偶数、含负数assertEquals(3.0, sol.findMedian(new int[]{3, -2, 7}), 1E-03); assertEquals(5.0, sol.findMedian(new int[]{-100, 99, 3, 0, 5, 7, 11, 66, -33}), 1E-03); assertEquals(4.5, sol.findMedian(new int[]{4, -100, 99, 3, 0, 5, 7, 11, 66, -33}), 1E-03);四、两种方案怎么选复杂度对比维度双堆法分治法值域二分内存O(n)需缓存约一半数据O(1)只存计数器I/O1 遍顺序读O(log V) 遍int 范围约 32 遍时间摊还 O(n log(n/2))O(V × log V)V 为文件行数适用场景数据流实时中位数文件可重复扫、内存极度受限扩展性支持动态插入数值范围大时轮次增多可先用采样估界面试实战建议先说双堆法展示流式思维再引出分治法解释内存放不下的兜底方案最后主动对比两者的取舍——这正是面试官想听的结构化表达。五、动手跑一遍本地验证测试项目基于 Gradle JUnit 4见 build.gradle克隆后在仓库根目录执行# 运行全部题目测试 ./gradlew test # 只跑中位数这一题 ./gradlew -Dtest.singleFindMedianinLargeIntegerFileofIntegers test⚙️ 环境要求Java 11、Gradle 5.6.3README.md Requirements 一节。六、延伸题库中值得对比练习的题中位数题考察的是受限 I/O 数据流处理题库里还有几道同类型的工程向题目建议搭配练习Display Page分页展示src/main/java/display_page/DisplayPage.java—— 同样是顺序处理大量结果考察在流上维护约束条件Menu Combination Sumsrc/main/java/menu_combination_sum/MenuCombinationSum.java—— 组合枚举类与分治思想相通Minimum Cost with At Most K Stopssrc/main/java/minimum_cost_with_at_most_k_stops/MinimumCostwithAtMostKStops.java—— 动态规划求最短路练 DP 基本功七、总结一张表记住核心结论大数据中位数 ≠ 排序后取中间顺序访问 内存受限必须靠状态维护或统计分治双堆法一遍流式读完即可查询代价是 O(n) 内存分治法值域二分O(1) 内存 约 32 遍扫描靠计数第 k 小收敛到答案细节决定正确性用真实值res收缩二分边界、奇偶长度分别处理都是官方解法的加分点掌握这套堆 分治的组合拳无论是海量整数文件中位数还是其他流式统计问题TopK、分位数、实时均值你都有了可迁移的解题模板。【免费下载链接】airbnb项目地址: https://gitcode.com/gh_mirrors/ai/airbnb创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考