在2.5亿个整数中找出不重复的整数，注：内存不足以容纳这2.5亿个整数。

Find the integers that appear exactly once among 250 million integers, given that memory is insufficient to hold all numbers.

题目类型: 技术面试题

这是一道技术面试题，常见于澳洲IT公司面试中。

难度: hard

分类: 大数据处理, 位图, 去重统计

标签: Bitmap, 2-bit Bitmap, Hash Partition, External Processing

参考答案摘要

核心答案 可用 2-bit Bitmap 精确记录出现次数状态，或采用 分桶 + 小文件统计 + 归并 。 方案1（2-Bitmap，精确） 每个数分配2bit： 00 表示不存在， 01 表示出现一次， 10 表示出现多次， 11 无意义。 所需内存： 2^32 × 2bit ≈ 1GB ，可接受。 扫描2.5亿整数： 位为00 → 改成01 位为01 → 改成10 位为10 → 保持不变 扫描...

本题提供 STAR 原则详细解答和技术解析，登录匠人学院学习中心即可查看完整答案。