位图算法面试题｜系统掌握 Bitmap 核心考点

⚡ 什么是位图（Bitmap）？

位图（Bitmap）是一种用1位（bit）表示一个元素是否存在的数据结构。其本质是一个紧凑的布尔数组，通过将每个元素映射到一个比特位，实现高效的存储与查询。

例如，若需表示数字集合 {1, 3, 5, 7}，可构建长度为 8 的位图（索引 0~7），置位对应位置：

# 索引： 0 1 2 3 4 5 6 7
# 位值： 0 1 0 1 0 1 0 1

即：第 i 位为 1 表示数字 i 存在，0 表示不存在。位图的核心优势在于：

• 空间高效：存储 n 个整数仅需 n/8 字节（1 字节 = 8 位）；
• 时间高效：插入、查找、删除均为 O(1)；
• 支持集合运算：可直接通过位运算实现并、交、差、异或。

⚙️ 基本操作实现（以 Java 为例）

位图通常用整型数组实现（如 int[]），每个整型占 32 位，可表示 32 个元素。

public class MyBitmap {
    private int[] data;
    public MyBitmap(int capacity) {
        // 每个 int 表示 32 位，向上取整
        data = new int[(capacity + 31) >>> 5];
    }
    public void set(int index) {
        // 定位所在 int：index / 32 → index >> 5
        // 定位位偏移：index % 32 → index & 31
        data[index >>> 5] |= (1 << (index & 31));
    }
    public boolean get(int index) {
        return (data[index >>> 5] & (1 << (index & 31))) != 0;
    }
    public void clear(int index) {
        data[index >>> 5] &= ~(1 << (index & 31));
    }
}

关键技巧：

• 右移 5 位等价于除以 32；
• 按位与 & 31（即 & 0x1F）等价于取模 32；
• 位运算比乘除法快 3~10 倍，是系统级编程常用优化。

📊 位图 vs 传统数据结构

结论：当元素值域较小（如 0 ~ 10⁶）、仅需存在性判断时，位图是空间最优解；若需动态增删、范围查询，可考虑 BitSet 或跳表。

〔1〕经典问题：判断整数是否存在

题目：给定 10 亿个无符号 32 位整数，如何快速判断某个整数是否存在？内存限制为 512MB。

分析：

• 10 亿整数需空间：10⁹ × 4 字节 = 4GB（直接存数组不现实）；
• 用位图：10⁹ 位 = 125MB（满足内存限制）；
• 哈希可能冲突，位图无冲突。

解法：构建位图，遍历所有数置位，查询时直接查位。

延伸追问：

• Q：若整数有负数怎么办？
  A：将整数映射到非负范围，如 x → x + 2³¹；或拆分正负两部分，分别建位图。
• Q：若内存仅 100MB？
  A：分块处理：按高位划分（如高 8 位分 256 块），每块独立建位图；或用布隆过滤器（牺牲精确性换空间）。

〔2〕缺失数字查找

题目：一个数组包含 0 ~ n 中缺失一个数字，其余数字不重复，如何在 O(n) 时间、O(1) 额外空间内找出缺失数？

陷阱：求和法会溢出（如 n=10⁹ 时 n(n+1)/2 超 int 范围）；异或法虽安全但仅适用于“缺一个”场景。

位图解法：

public int findMissing(int[] nums) {
    int n = nums.length;
    MyBitmap bitmap = new MyBitmap(n + 1);
    for (int num : nums) {
        bitmap.set(num);
    }
    for (int i = 0; i <= n; i++) {
        if (!bitmap.get(i)) return i;
    }
    return -1;
}

优化：若仅缺一个数，可直接用异或（空间 O(1)），但位图通用性更强（如缺多个数时仍适用）。

〔3〕重复数字查找（进阶）

题目：数组包含 1 ~ n 中 n+1 个整数，必有至少一个重复，找出任意一个重复数（不能修改数组，空间 O(1)）。

位图解法：若允许用位图（空间 O(n)），直接记录是否出现过，首次重复即返回。但题目限制空间 O(1)，需用二分搜索 + 计数思想（非位图）。

位图适用前提：值域可控且内存充足。若值域过大（如 int 全范围），位图不现实，应考虑其他算法（如哈希、抽样）。

〔4〕Top-K 问题变体

题目：1 亿个整数中，找出出现次数最多的前 10 个数（内存 256MB）。

位图局限：位图仅记录存在性，不记录频次。需扩展为“计数位图”（Counting Bitmap）：

• 用 2 位表示频次：00（0）、01（1）、10（2）、11（≥3）；
• 空间翻倍，但支持粗略频次统计。

更优方案：用 HashMap 统计频次 + 最小堆（空间 O(k)），位图仅作辅助（如判断是否首次出现）。

〔5〕排序问题（外部排序）

题目：10 亿个无符号整数排序（内存 1GB）。

位图排序：

1. 扫描所有数，置位位图；
2. 遍历位图，输出所有为 1 的索引（自动有序）。

时间复杂度：O(n + U)（U 为值域大小）；

空间复杂度：O(U/8)；

注意：仅适用于 U 较小（如 U ≤ 10⁹）。若 U = 2³²，位图需 512MB，勉强可行；若 U 更大，需分块排序（外部排序）。

〈例1〉查找缺失的 32 位整数

场景：磁盘有 40 亿个随机 32 位整数（无序），求未出现的最小整数。

思路：用位图标记存在性，扫描位图找第一个 0 位。

代码：

public int findFirstMissing(long[] nums) {
    int capacity = 1 << 32; // 2^32
    long[] bitmap = new long[(capacity + 63) >>> 6]; // 每 long 64 位
    for (long num : nums) {
        int idx = (int) (num >>> 6);
        int bit = (int) (num & 63);
        bitmap[idx] |= (1L << bit);
    }
    for (int i = 0; i < bitmap.length; i++) {
        if (bitmap[i] != -1L) { // 全 1 才为 -1
            for (int j = 0; j < 64; j++) {
                if ((bitmap[i] & (1L << j)) == 0) {
                    return (i << 6) + j;
                }
            }
        }
    }
    return -1;
}

优化点：

• 用 long 数组（每元素 64 位）减少数组长度；
• 避免重复计算位索引；
• 提前终止：若某块未全满，立即扫描其位。

〈例2〉去重并排序 100 万整数

输入：100 万个整数（范围 0 ~ 999999），可能有重复。

输出：去重后的升序序列。

解法：

int capacity = 1000000;
MyBitmap bitmap = new MyBitmap(capacity);
// 插入并自动去重
for (int num : input) {
    bitmap.set(num);
}
// 收集结果（天然有序）
List<Integer> result = new ArrayList<>();
for (int i = 0; i < capacity; i++) {
    if (bitmap.get(i)) {
        result.add(i);
    }
}

对比：

结论：当 U 较小（如 U ≤ 10⁷），位图更快；否则优先排序或哈希。

〈例3〉集合交集计算（内存受限）

题目：两个文件各存 1 亿个整数，求交集（内存 ≤ 200MB）。

位图解法：

1. 读文件1，构建位图 A（需 125MB）；
2. 读文件2，对每个数查位图 A，若存在则输出（不存交集，流式输出）；
3. 总内存：125MB（A） + 少量缓冲区。

对比：

• 哈希法需建两个哈希表（约 2×4GB），内存不足；
• 排序法需外部排序（I/O 多），速度慢。

变体：若交集较大需存盘，可分块：按高位划分文件（如高 8 位分 256 块），每块独立求交集。

〔布隆过滤器 vs 位图〕

布隆过滤器（Bloom Filter）是位图的扩展，支持更大数据集的近似存在性判断。

public class BloomFilter {
    private final int numHashFunctions;
    private final MyBitmap bitmap;
    public BloomFilter(int expectedInsertions, double fpp) {
        int numBits = (int) (-expectedInsertions * Math.log(fpp) / (Math.log(2) * Math.log(2)));
        numHashFunctions = Math.max(1, (int) Math.ceil((numBits / expectedInsertions) * Math.log(2)));
        bitmap = new MyBitmap(numBits);
    }
    public void add(int item) {
        int hash1 = item.hashCode();
        for (int i = 0; i < numHashFunctions; i++) {
            bitmap.set((hash1 + i * 2654435761) & bitmap.capacity());
        }
    }
    public boolean mightContain(int item) {
        int hash1 = item.hashCode();
        for (int i = 0; i < numHashFunctions; i++) {
            if (!bitmap.get((hash1 + i * 2654435761) & bitmap.capacity())) {
                return false;
            }
        }
        return true;
    }
}

〔HyperLogLog vs 位图〕

HyperLogLog 用于基数估计（如统计独立访客数），空间仅需 O(log log n)。

〔跳表 vs 位图〕

跳表（Skip List）支持动态有序集合，适合值域大、需范围查询的场景。

位图 vs 跳表：

• 位图：静态、空间高效、无范围查询；
• 跳表：动态、支持插入/删除、范围查询 O(log n + k)；
• 若需频繁更新集合，跳表更优；若仅需一次构建后多次查询，位图更高效。

〈延伸思考〉位图在数据库中的应用

现代数据库（如 PostgreSQL、ClickHouse）使用位图索引加速查询：

• 对低基数列（如性别：男/女）建位图索引；
• 查询时直接位运算（如 WHERE gender='F' AND age>30）；
• 索引大小仅为原始数据的 1%~10%。

典型场景：电商用户画像分析（用户属性组合筛选）。