如何扩展猜数卡片数组 扩大预测范围且保持O(log(n))复杂度

原有逻辑核心本质 #

你提到的卡片猜数字本质是利用了二进制的位特征：

• 每张Card#k（k从0开始计数）的首个数字固定为2^k，5张卡片刚好对应二进制的低5位，覆盖范围是1~2^5 -1 = 31
• 某个数字如果二进制的第k位值为1，就会被放进Card#k中，最终把出现卡片的首数字相加，本质就是把二进制位为1的位权相加，自然得到原数字

扩展实现步骤 #

扩展不需要修改原有核心逻辑，只需要按照固定规则生成新卡片即可，全程保持O(log n)的时间复杂度：

• 步骤1：确定需要的卡片总数
  如果你要覆盖的最大数字是N，需要的卡片总数为⌈log₂(N+1)⌉，比如要覆盖1~127，就需要7张卡片，在原有5张基础上新增Card#5、Card#6即可。
• 步骤2：生成新卡片内容
  新卡片完全遵循原有卡片的生成规则：
  1. 编号为k的卡片Card#k首数字固定为2^k，比如Card#5首数字为32，Card#6首数字为64
  2. 遍历目标范围内的所有数字，只要数字的二进制表示第k位为1，就把该数字放入Card#k中
• 步骤3：保持原有猜数字逻辑不变
  猜数字时依旧只需要用户告知数字出现的卡片编号，把对应卡片的首数字相加就能得到结果，计算次数等于卡片数量，始终是目标范围的对数级，时间复杂度保持O(log n)。

扩展示例 #

比如新增Card#5后可覆盖范围扩大到1~63，Card#5包含的数字为所有二进制第5位为1的数：32,33,34,...,63。比如数字50的二进制为110010，第1、4、5位为1，对应出现在Card#1、Card#4、Card#5，首数字相加为2+16+32=50，符合规则。

内容的提问来源于stack exchange，提问作者Adan Gomez