Skip to content

Latest commit

 

History

History
16 lines (10 loc) · 893 Bytes

count-different-phone-numbers.md

File metadata and controls

16 lines (10 loc) · 893 Bytes

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

题目描述

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

解答思路

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

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

思路如下

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

方法总结

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