题目描述: 将中国的百家姓按一定规则进行存储, 1.存储容器为一个圆盘,将圆盘等量分为7份,每一个分片上存储若干个姓氏 2.随机指定某个姓氏,对7个分片逐个进行访问,每个分片都会返回true/false告诉你这个姓氏是否在这个分片上,7个分片全部询问结束后,你就可以知道指定的是哪个姓氏了 要求:对这些分片存储姓氏的规则进行合理编排以满足上诉两条规则
看到这个题目首先想到的是布隆过滤器,但是布隆过滤器只能判断给定姓氏一定不存在和可能存在,无法判断这个姓氏一定存在,所以这个方案pass了, 仔细研究下题目,发现它有个遍历询问的过程,然后给出最终确定答案,是不是感觉和「小白鼠试毒药」问题很像呢,简直是异曲同工之妙呀~ 话不多说,直接给思路吧
将给定的大圆盘平均分为7份,排号为1-7 设定:
每一个分片上都可以存储1个或者若干个姓氏一个姓氏可以被存储多次对每个姓氏进行初始化编码,最简单的就是按照顺序排列,假定有100个姓氏,按照0-99给定编码,将每个编码转成7为的二进制数,高位用0补齐,因为2的7次方是128,所以完全可以满足条件 举例: 肖在百家姓排名中占第30位,那么 肖 姓的编号就是 30 转成7位二进制: 001 1110 二进制数与7个分片对照起来, 位置是1的对应分片存储这个字 (从左到右)
分片1分片2分片3分片4分片5分片6分片70011110❌❌存储存储存储存储❌按照这个规则,将100个姓氏都进行编排存储
对指定的某个姓氏进行判断的时候,只需要根据分片返回的true/false true: 1 false: 0 按照规则拼装出对应7二进制数字,再转回10进制编码,就可以确定这个姓氏是哪个啦 是不是很简单呢!!
[注1] 这道题和「小白鼠试毒药」的原理相同,面试时可能还会有其他场景的变形,只要确定用二进制位数确定唯一值的原理就都可以引刃而解啦 [注2] 中国的百家姓远不止100个这个多,这里只是用作举例说明,如果想要表示更多的姓氏,只需要增加分片的数量即可
