menu

count-different-phone-numbers

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

题目描述

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

解答思路

这道题本质还是求解数据重复的问题,对于这类问题,一般首先考虑位图法。

对于本题,8 位电话号码可以表示的号码个数为 108 个,即 1 亿个。我们每个号码用一个 bit 来表示,则总共需要 1 亿个 bit,内存占用约 12M。

思路如下

申请一个位图数组,长度为 1 亿,初始化为 0。然后遍历所有电话号码,把号码对应的位图中的位置置为 1。遍历完成后,如果 bit 为 1,则表示这个电话号码在文件中存在,否则不存在。bit 值为 1 的数量即为 不同电话号码的个数。

方法总结

求解数据重复问题,记得考虑位图法。


评论:


技术文章推送

手机、电脑实用软件分享

微信搜索公众号: AndrewYG的算法世界
wechat 微信公众号:AndrewYG的算法世界