面试问题：对于数组中的每个数字，找出它与任何其他数字的最大位差

Question

我最近遇到这个问题，不知道如何解决。n1我得到了一个小于一百万的正整数数组，对于每个数字，我必须计算它与数组中任何其他数字的最大位差，其中和之间的位差n2被定义为设置位的数量在n1 xor n2。例如，输入

3 (011)
5 (101)
4 (100)

应该输出数组

3 (3 ^ 4 = 7, which has 3 set bits)
2 (5 ^ 3 = 6, which has 2 set bits)
3 (4 ^ 3 = 7, which has 3 set bits)

其中输出数组中的每个数字对应于包含输入数组中具有相同索引的输入的所有对的最大位差（因此，例如，用于第一个索引处的输出的对必须包括 3，因为 3 是输入数组中的第一个数字。）数组的大小可能非常大，因此我认为每对的 O(N^2) 解决方案太慢了。我怀疑该解决方案与利用数字必须小于 100 万这一事实有关，因为这意味着每个数字只有 20 位。然而，我无法继续这个想法。

Answer 1

伊恩·默瑟既聪明又正确。我将解释为什么二叉树可以工作，其中每个节点向左/向右移动取决于是否有 0 或 1。

探索树的操作总是比暴力破解要少。但蛮力操作是xor运行速度极快的操作。树获胜的地方在于，在一个很长的列表上，您可能不会对其进行太多探索，而蛮力确实与列表大小的平方成正比。

让我们对此建立一些直觉。这个范围内的两个随机数几乎是两个20位的随机集合。因此，它们的按位差是 20 次抛硬币的总和。m我们可以轻松计算二项式分布（位差异的概率为(20 choose m) / 2^20），我们发现差异的几率为：

0 differences = 0.000000956...
1 differences = 0.000019073...
2 differences = 0.000181198...
3 differences = 0.001087188...
4 differences = 0.004620552...
5 differences = 0.014785766...

因此，如果我们的列表有超过 5500 个元素，我们就有很大的机会只探索树中最多有 2 个差异的部分，而且这个差异并不大。

如果它有超过 1000 个元素，我们很可能不需要考虑超过 3 个差异。这可能仍然比暴力更好。当我们确实必须考虑 4 的差异时，我粗略地猜测，暴力破解会更好。但我们可以聪明一点，从树中 4 位差异的部分开始，其中第三个差异尽可能晚。因此我们不必过多查看树的 4 位差异部分。

如果列表的元素少于 200 个，我们可能需要探索树中 5 个以上的差异。蛮力可能更快。（xor速度快得令人难以置信！）但是现在整棵树并没有那么大，所以我们并不真正关心性能。