page contents

如何统计不同电话号码的个数?

轩辕小不懂 发布于 2021-10-08 11:14
阅读 1345
收藏 0
分类:Golang

已知某个文件内包含一些电话号码,每个号码为8位数字,统计不同号码的个数。

2099
Nen
Nen
- 程序员

分析解答:这个题目从本质上而言也是求解数据重复的问题,一般而言,对于这类问题首先会考虑位图法。对于本题而言,8位电话号码可以表示的范围为:0000 0000~99999999,如果用1bit表示一个号码,总共需要1亿个bit,大约100MB的内存。

通过上面的分析可知,这道题的主要思路为:申请一个位图并初始化为0,然后遍历所有电话号码,把遍历到的电话号码对应的位图中的bit设置为1。当遍历完成后,如果bit值为1则表示这个电话号码在文件中存在,否则这个bit对应的电话号码在文件中不存在。所以bit值为1的数量就是不同电话号码的个数。

那么对于这道题而言,最核心的算法是如何确定电话号码对应的是位图中的哪一位。下面重点介绍这个转化的方法,这里使用下面的对应方法。

00000000对应位图最后一位:0x0000…000001。

00000001对应位图倒数第二位:0x0000…0000010(1向左移一位)。

00000002对应位图倒数第三位:0x0000…0000100(1向左移2位)。

00000012对应位图的倒数十三位:0x0000…0001 0000 0000 0000。

通常,位图都是通过一个整数数组来实现的(这里假设一个整数占用4个字节)。由此可以得出通过电话号码获取位图中对应位置的方法为(假设电话号码为P):

(1)通过P/32就可以计算出该电话号码在bitmap数组的下标(因为每个整数占用32bit,通过这个公式就可以确定这个电话号码需要移动多少个32位,也就是可以确定它对应的bit在数组中的位置)。

(2)通过P%32就可以计算出这个电话号码在这个整型数字中具体的bit的位置,也就是1这个数字对应的左移次数。因此可以通过把1向左移P%32位,然后将得到的值与这个数组中的值做或运算,这样就能把这个电话号码在位图中对应的位设置为1。

(3)这个转换的操作可以通过一个非常简单的函数来实现:

attachments-2021-10-9KsGPLGL615fbb0d267d2.jpg

请先 登录 后评论