1.统计不同号码的个数
2023/4/9大约 2 分钟
题目描述
已知某个文件内包含大量电话号码,每个号码为8位数字,如何统计不同号码的个数?
思路分析
这类题目其实是求解数据重复的问题。对于这类问题,可以使用位图法处理
8位电话号码可以表示的范围为00000000~99999999。如果用 bit表示一个号码,那么总共需要1亿个bit,总共需要大约10MB的内存。
申请一个位图并初始化为0,然后遍历所有电话号码,把遍历到的电话号码对应的位图中的bit设置为1。当遍历完成后,如果bit值为1,则表示这个电话号码在文件中存在,否则这个bit对应的电话号码在文件中不存在。
最后这个位图中bit值为1的数量就是不同电话号码的个数了。
那么如何确定电话号码对应的是位图中的哪一位呢?
可以使用下面的方法来做电话号码和位图的映射。
00000000 对应位图最后一位:0×0000…000001。
00000001 对应位图倒数第二位:0×0000…0000010(1 向左移 1 位)。
00000002 对应位图倒数第三位:0×0000…0000100(1 向左移 2 位)。
……
00000012 对应位图的倒数第十三位:0×0000…0001 0000 0000 0000(1 向左移 12 位)。
也就是说,电话号码就是1这个数字左移的次数。
具体实现
首先位图可以使用一个int数组来实现(在Java中int占用4byte)。
假设电话号码为 P,而通过电话号码获取位图中对应位置的方法为:
第一步,因为int整数占用4*8=32bit,通过 P/32 就可以计算出该电话号码在 bitmap 数组中的下标,从而可以确定它对应的 bit 在数组中的位置。
第二步,通过 P%32 就可以计算出这个电话号码在这个int数字中具体的bit的位置。只要把1向左移 P%32 位,然后把得到的值与这个数组中的值做或运算,就可以把这个电话号码在位图中对应的位设置为1。
以00000100号码为例。
- 首先计算数组下标,100 / 32 = 3,得到数组下标位3。
- 然后计算电话号码在这个int数字中具体的bit的位置,100 % 32 = 4。取余为0左移1位,故取余为4左移5位,得到000...000010000
- 将位图中对应的位设置为 1,即arr[2] = arr[2] | 000..00010000。
- 这就将电话号码映射到了位图的某一位了。
最后,统计位图中bit值为1的数量,便能得到不同电话号码的个数了。