arrays - 数组中异或最大的两个元素

Question

给定一个整数数组，您必须找到 XOR 最大的两个元素。

有一种天真的方法——只需选择每个元素并与其他元素进行异或运算，然后比较结果以找到对。

除此之外，还有什么有效的算法吗？

Answer 1

我想我有一个 O(n lg U)算法，其中 U是最大的数字。这个想法类似于 user949300 的，但有更多的细节。
直觉如下。当您对两个数字进行异或运算时，要获得最大值，您需要一个 1在可能的最高位置，然后是具有 1 的配对在这个位置，您需要与 1 配对在下一个可能的最高位置，等等。
所以算法如下。首先找到最高的 1数字中的任何位置(您可以通过对每个 O(n lg U) 数字执行 O(lg U) 工作来及时执行此操作 n)。现在，将数组分成两部分 - 其中一个具有 1 的数字在那位和组0在那一点。任何最优解都必须将一个数字与一个 1 结合起来。在第一个带有 0 的数字的位置在那个位置，因为那会放一个 1尽可能高一点。任何其他配对都有 0那里。
现在，递归地，我们想从 1 中找到数字对。和 0最高的组1在他们之中。为此，在这两组中，将它们分成四组:

以 11 开头的数字

以 10 开头的数字

以 01 开头的数字

以 00 开头的数字

如果 11中有任何数字和 00组或在 10和 01组，他们的 XOR 将是理想的(从 11 开始)。因此，如果这些组对中的任何一组不为空，则从这些组递归计算理想解决方案，然后返回这些子问题解决方案的最大值。否则，如果两个组都为空，这意味着所有数字的第二个位置必须具有相同的数字。因此，以 1 开头的数字的最佳 XOR和一个以 0 开头的数字最终将取消下一个第二位，所以我们应该只看第三位。
这给出了以下递归算法，从按其 MSB 划分的两组数字开始，给出答案:

给定组1和组0和位索引 i :

如果位索引等于位数，则返回 1 中(唯一)数的异或。组和 0 中的(唯一)编号团体。

构造组11 , 10 , 01 , 和 00来自那些群体。

如组11和组00是非空的，递归地找到这两组的最大异或，从位 i + 1 开始.

如组10和组01非空，递归地找出这两组的最大异或，从位 i + 1 开始.

如果上述任何一种配对都是可能的，则返回递归找到的最大配对。

否则，所有数字的位置 i 必须具有相同的位。 ，因此返回通过查看位 i + 1 找到的最大对上群 1和 0 .

要开始算法，您实际上可以将初始组中的数字分成两组 - 带有 MSB 1 的数字。和带有 MSB 的数字 0 .然后，您使用两组数字对上述算法进行递归调用。
例如，考虑数字 5 1 4 3 0 2 .这些有代表

101  001  100   011   000   010

我们首先将它们分成 1组和 0团体:

101  100
001  011  000  010

现在，我们应用上述算法。我们将其分成几组 11 , 10 , 01 , 和 00 :

11:
10:  101  100
01:  011  010
00:  000  001

现在，我们无法配对任何 11带有 00 的元素元素，所以我们只是在 10 上递归和 01组。这意味着我们构造了 100 , 101 , 010 , 和 011团体:

101: 101
100: 100
011: 011
010: 010

现在我们只剩下一个元素的桶，我们可以检查对 101和 010 (给出 111 )和 100和 011 (这给出了 111 )。任何一个选项在这里都有效，所以我们得到最佳答案是 7 .
让我们考虑一下这个算法的运行时间。请注意，最大递归深度为 O(lg U) ，因为只有 O(log U)数字中的位。在树的每一层，每个数字恰好出现在一个递归调用中，并且每个递归调用的工作量与 0 中的数字总数成正比。和 1组，因为我们需要按位分配它们。因此，有 O(log U)递归树中的级别，每个级别都做 O(n)工作，总工作量 O(n log U) .
希望这可以帮助!这是一个很棒的问题!