考点
数据结构-排序-堆排序
面5笔5某地电信局要对业务号码进行梳理，需要检测开通的市话号码是否存在某一个是另一个的前缀的情况，以简化电话交换机的逻辑。例如：某用户号码是“11001100”，但与"110"报警电话产生前缀配对。已知市话号码最长8位，最短3位，并且所有3位的电话号码都以1开头。由于市话号码众多，长度也未必一直，高效的算法可以用O(n)的时间复杂度完成检测（n为开通市话号码个数，数量是千万级的）。那么，该算法最坏情况下需要耗费大约________内存空间
A.5GB
B.500MB
C.50MB
D.5MB
前往“校招VIP”小程序，刷题更快
最新校招难题刷题，快来进刷题群吧
解答
正确答案是 C
最长 8 位, 最短 3 共6种情况：
- 三位都是 1 开头 ,因此有 10^2=100 种
- 四位： 10^4=10，000 种
- 五位： 10^5=100，000 种
- 六位： 10^6=1，000，000 种
- 七位： 10^7=10，000，000 种
- 八位： 10^8=100，000，000种
相加一共为111，110，100种，因为电话号码唯一，所有号码最后1位不用判断，总数除以10 = 11,111,010种
一位号码 4bit（号码 从 0-9 ，所以至少用 4 个 bit 位才能表示 ），8位的号码占 32bit 即 4字节/byte（其实可以只存前7位,3.5byte）
最后：11,111,010 * 4 / 1024 / 1024 = 42.4 Mb
猪猪猪
2018-10-13 15:45:16
0
0
遇见
2018-10-13 15:45:00
0
0
老干妈拌面
2018-10-13 15:44:32
0
0
小飞鞋
2018-10-13 15:44:12
0
0
米米大户
2018-10-13 15:43:54
0
0
繁星知晓
2018-10-13 15:43:32
0
0
