面试题,程序员面试题,Java面试题,算法,统计不同电话号码的个数,数据重复问题,位图法

题目描述

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

解答思路

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

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

思路如下

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

方法总结

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

标签: Java面试题, 面试题, 程序员面试题, 算法, 位图法, 统计不同电话号码的个数, 数据重复问题

添加新评论