统计不同号码的个数

题目描述

已知某个文件内包含大量电话号码，每个号码为 8 位数字，如何统计不同号码的个数？内存限制 100M。

解决方案

8 位电话号码可以表示的范围为 00000000～99999999。如果用 bit 表示一个号码，那么总共需要 1 亿个 bit，总共需要大约 10MB 的内存。

申请一个位图并初始化为 0，然后遍历所有电话号码，把遍历到的电话号码对应的位图中的 bit 设置为 1。当遍历完成后，如果 bit 值为 1，则表示这个电话号码在文件中存在，否则这个 bit 对应的电话号码在文件中不存在。

最后这个位图中 bit 值为 1 的数量就是不同电话号码的个数了。

具体实现

# 初始化位图
bit_map = [0] * (10**8 // 8)
 
# 读取文件
with open('phone_numbers.txt', 'r') as file:
    for line in file:
        phone_number = int(line.strip())
        # 计算对应的字节索引和比特位索引
        byte_index = phone_number // 8
        bit_index = phone_number % 8
        # 将对应的比特位置为 1
        bit_map[byte_index] |= (1 << bit_index)
 
# 统计不同号码个数
unique_count = 0
for byte in bit_map:
    # 统计字节中值为 1 的比特位个数
    unique_count += bin(byte).count('1')
 
print(f"不同号码的个数为: {unique_count}")