40亿QQ号, 1G内存，怎么去重？

#### **问题分析** - **数据量**：40亿个QQ号，每个QQ号用32位整数（4字节）表示。 - **直接存储内存需求**： $$ 40亿 \times 4 \, \text{字节} = 16 \, \text{GB} $$ 超过了1GB的限制。 - **目标**：在1GB内存限制下实现去重。 #### **方案1：使用BitMap进行去重** ##### **BitMap的核心思路** - 使用**位图（BitMap）**，用每个bit表示一个QQ号是否出现过。 - 1个bit表示一个QQ号，40亿个QQ号需要： $$ 40亿 \div 8 = 500 \, \text{MB} $$ 内存，完全满足1GB限制。 ##### **具体实现步骤** 1. **初始化位图：** - 创建一个大小为40亿bit的位数组（约500MB）。 - 位图初始状态每一位都为0，表示这些号码尚未出现。 2. **读取QQ号并标记位图：** - 遍历输入的QQ号列表。 - 每读取一个QQ号，将其映射到位图中的对应位置，将该位置的bit设为1。 - 如果某个bit已经为1，表示该QQ号已出现过，不需要再处理。 3. **输出去重后的结果：** - 遍历位图，找到所有bit为1的位置，这些位置对应的QQ号即为去重后的结果。 ##### **示例代码（伪代码）** ```java int N = 4_000_000_000; // QQ号最大范围 BitSet bitMap = new BitSet(N); // 初始化位图 for (int qq : qqNumbers) { bitMap.set(qq); // 将对应位标记为1 } for (int i = 0; i < N; i++) { if (bitMap.get(i)) { System.out.println(i); // 输出去重后的QQ号 } }