这是对aix答案的改进。考虑对数据结构使用三个“层”：第一个是前五个数字（17位）的常量；因此从这里开始，每个电话号码只剩下剩余的五位数。我们将剩下的五个数字视为17位二进制整数，并使用一种方法存储这些位的
k ，使用另一种方法存储17- k = m ，最后确定 k 以最小化所需的空间。

我们首先对电话号码进行排序（所有电话号码均减少为5个十进制数字）。然后，我们看看有多少电话号码有针对由第一的二进制数 米
位都是0，对于电话多少个号码第一 米 位至多0 … 01，进行电话多少个号码第一 米 位最多为0 … 10，以此类推，直到前 m 位为1
… 11 的电话号码计数为止-最后一个计数为1000（十进制）。有2 ^ m个
这样的计数，每个计数最多为1000。如果我们省略最后一个计数（因为无论如何我们都知道是1000），则可以将所有这些数字存储在（2 ^ m
-1）的连续块中* 10位。（10位足以存储小于1024的数字。）

所有（减少的）电话号码的最后 k 位连续存储在内存中；因此，如果 k
为7，则该存储块的前7位（位0至6）对应于第一个（减少的）电话号码的后7位，位7至13对应于后7位第二个（减少的）电话号码等。这需要1000 * k
位，总共17 +（2 ^（17- k ）-1）* 10 + 1000 * k ，对于 k = 10
，其最小值为11287。因此，我们可以将所有电话号码存储在ceil（ 11287/8）= 1411个字节。

观察到我们的数字都不能以例如1111111（二进制）开头，这可以节省更多空间，因为以该数字开头的最低数字是130048，而我们只有五个十进制数字。这使我们可以从第一块内存中删除一些条目：我们只需要ceil（99999/2
^ k ）来代替2 ^ m -1个计数。这意味着公式变为 __

17 + ceil（99999/2 ^ k ）* 10 + 1000 * k

对于 k = 9和 k = 10或ceil（10997/8）= 1375字节，这足以达到其最小值10997 。

如果我们想知道某个电话号码是否在我们的电话机中，请首先检查前五个二进制数字是否与我们存储的五个数字匹配。然后，我们将剩余的五位数字分成高位的 m =
7位（即 m 位数字 M ）和低位的 k = 10位（数字 K ）。我们现在发现的数量 一 减少电话号码，第一[M-1] 米
的数字是最多 中号 - 1，数 一 [M]减少的电话号码，其中第一个 米 的数字是最多 中号 ，都来自第一个位块。现在我们之间签 一个
[M-1]和第 一个 [M]的第序列 ķ 在存储器的第二块的比特，以查看是否发现 ķ ;
在最坏的情况下，有1000个这样的序列，因此，如果使用二进制搜索，则可以完成O（log 1000）个操作。

下面是用于打印所有1000个数字的伪代码，在这里我 以 [K]的形式访问第一个存储块的第 K 个 k 位条目，以 b
[M]形式访问第二个存储块的第 M 个 m 位条目。（这两者都需要进行一些乏味的写操作）。前五位数字为 c 。 __

i := 0;
for K from 0 to ceil(99999 / 2^k) do
  while i < a[K] do
    print(c * 10^5 + K * 2^k + b[i]);
    i := i + 1;
  end do;
end do;

边界条件 K = ceil（99999/2 ^ k ）可能出了些问题，但这很容易解决。

最后，从熵的角度来看，不可能在少于ceil（log [2]（binomial（10 ^ 5，10 ^ 3））的情况下存储全部小于10 ^5的10^3个正整数的子集）=8073。包括前5位数字所需的17，仍然存在10997-8090 =
2907位的间隔。看看是否存在更好的解决方案，您仍然可以相对有效地访问数字，这是一个有趣的挑战！