内存有限，已知两个超大规模手机号码数据集合，每个集合存储为一个文件,找出集合 A 和集合 B 交集,并集,差集.

### **解决方案：Bitmap 实现并集、交集和差集** #### **核心思想** - **位图（Bitmap）：** 使用位数组，每个号码对应一个位，位为 1 表示号码存在。 - **交集：** `BitmapA & BitmapB` - **并集：** `BitmapA | BitmapB` - **差集：** `BitmapA & ~BitmapB` #### **实现步骤** 1. 将两个文件（集合 A 和集合 B）逐行读取，分别存入两个位图。 2. 针对不同操作（交集、并集、差集），进行按位运算： - **交集：** 遍历位图，对两个位图执行按位与操作，结果为 1 的位置即为交集。 - **并集：** 遍历位图，对两个位图执行按位或操作，结果为 1 的位置即为并集。 - **差集：** 遍历位图，对第一个位图和第二个位图的取反按位与操作，结果为 1 的位置即为差集。 3. 将结果位图中的位置转化为号码并输出到文件。 ### **代码实现** #### **Java代码** ```java import java.io.*; import java.util.BitSet; public class BitmapSetOperations { private static final long MAX_NUM = 1L << 32; // 支持号码范围 [0, 2^32 - 1] public static void main(String[] args) throws IOException { BitSet bitSetA = new BitSet((int) MAX_NUM); BitSet bitSetB = new BitSet((int) MAX_NUM); // 加载集合 A 到 Bitmap loadToBitmap("fileA.txt", bitSetA); // 加载集合 B 到 Bitmap loadToBitmap("fileB.txt", bitSetB); // 求交集 BitSet intersection = (BitSet) bitSetA.clone(); intersection.and(bitSetB); saveFromBitmap(intersection, "intersection.txt"); // 求并集 BitSet union = (BitSet) bitSetA.clone(); union.or(bitSetB); saveFromBitmap(union, "union.txt"); // 求差集（A - B） BitSet difference = (BitSet) bitSetA.clone(); difference.andNot(bitSetB); saveFromBitmap(difference, "difference.txt"); } // 将文件中的号码加载到 Bitmap private static void loadToBitmap(String fileName, BitSet bitSet) throws IOException { try (BufferedReader reader = new BufferedReader(new FileReader(fileName))) { String line; while ((line = reader.readLine()) != null) { long number = Long.parseLong(line.trim()); bitSet.set((int) number); } } } // 将 Bitmap 中的结果保存到文件 private static void saveFromBitmap(BitSet bitSet, String fileName) throws IOException { try (BufferedWriter writer = new BufferedWriter(new FileWriter(fileName))) { for (int i = bitSet.nextSetBit(0); i >= 0; i = bitSet.nextSetBit(i + 1)) { writer.write(String.valueOf(i)); writer.newLine(); } } } } ``` ### **代码解释** 1. **Bitmap 构造：** - `BitSet` 是 Java 提供的位数组实现，用于高效存储布尔值。 - 将文件中的号码逐行读取，转换为整数后设置对应位为 `1`。 2. **交集 (`and`)：** - `intersection.and(bitSetB)`：对集合 A 和集合 B 执行按位与操作。 - 输出结果文件为 `intersection.txt`。 3. **并集 (`or`)：** - `union.or(bitSetB)`：对集合 A 和集合 B 执行按位或操作。 - 输出结果文件为 `union.txt`。 4. **差集 (`andNot`)：** - `difference.andNot(bitSetB)`：对集合 A 和 B 的取反执行按位与操作。 - 输出结果文件为 `difference.txt`。 ### **性能分析** 1. **空间复杂度：** - Bitmap 大小为 `2^32 / 8 = 512 MB`，单机内存能承受。 2. **时间复杂度：** - 加载文件到 Bitmap：`O(n)`。 - 按位运算（交集、并集、差集）：`O(m)`（Bitmap 的遍历复杂度，与位图大小相关）。 3. **适用范围：** - 数据范围大，但号码分布密集时最优。 - 若号码非常稀疏（分布范围远小于 `2^32`），可通过哈希表优化存储。 ### **总结** - **交集：** `BitmapA & BitmapB` - **并集：** `BitmapA | BitmapB` - **差集：** `BitmapA & ~BitmapB` 位图方案非常适合这种大规模集合运算，能够高效完成任务，并减少内存占用。