其异或为最大的数组两个元素 [英] Two elements in array whose xor is maximum

问题描述

由于整数数组，你必须要找到两个元素的XOR是最大的。

Given an array of integers ,You have to find two elements whose XOR is maximum.

有采摘每个元素与其它元素进行异或运算，然后比较结果找到一双--just幼稚的做法。

There is naive approach --just by picking each element and xoring with other elements and then comparing the results to find the pair.

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

Other than this ,Is there any efficient algorithm?

推荐答案

我想我有一个为O（n LG U）的算法对于这一点，其中U是人数最多的。我们的想法是类似user949300的，但有一个更详细一点。

I think I have an O(n lg U) algorithm for this, where U is the largest number. The idea is similar to user949300's, but with a bit more detail.

的直觉如下。当你进行异或两个数，以获得最大的价值，你想有一个1在尽可能高的位置，有一个1，在这个位置上配对的话，你希望在下次用1配对可能的最高位置，等等。

The intuition is as follows. When you're XORing two numbers together, to get the maximum value, you want to have a 1 at the highest possible position, and then of the pairings that have a 1 at this position, you want a pairing with a 1 at the next possible highest position, etc.

因此​​，算法如下。通过任何地方发现了数最高的1位开始（您可以通过执行O（LG U）每一个的n个数的工作时间为O（n LG U）做到这​​一点）。现在，分裂阵列分为两片 - 具有1在该位和组0在该位的数目中的一个。任何最优解必须结合一个号码与1中的第一点与一些具有0在这个位置，因为这将放一个1比特尽可能高。任何其他配对有0那里。

So the algorithm is as follows. Begin by finding the highest 1 bit anywhere in the numbers (you can do this in time O(n lg U) by doing O(lg U) work per each of the n numbers). Now, split the array into two pieces - one of the numbers that have a 1 in that bit and the group with 0 in that bit. Any optimal solution must combine a number with a 1 in the first spot with a number with a 0 in that spot, since that would put a 1 bit as high as possible. Any other pairing has a 0 there.

现在，递归，我们要查找的1和0组具有最高1一些数字的配对。这两个群体要做到这一点，分裂成四组：

Now, recursively, we want to find the pairing of numbers from the 1 and 0 group that has the highest 1 in them. To do this, of these two groups, split them into four groups:

• 在开始11号
• 在开始10号
• 在开始与01号
• 在开始00号

如果有在11和00组，或在10和01组的任何数字，它们的异或将是理想的（从11）。因此，如果任一者对组的不是空的，递归计算从这些组中提供了理想的解决方案，则返回那些子问题的解决方案中的最大值。否则，如果两个组是空的，这意味着所有的号码必须具有相同的数字在其第二位置。因此，一些从1开始的最佳XOR和一个数字从0开始就会有接下来的第二位抵消，所以我们应该看第三位。

If there are any numbers in the 11 and 00 group or in the 10 and 01 groups, their XOR would be ideal (starting with 11). Consequently, if either of those pairs of groups isn't empty, recursively compute the ideal solution from those groups, then return the maximum of those subproblem solutions. Otherwise, if both groups are empty, this means that all the numbers must have the same digit in their second position. Consequently, the optimal XOR of a number starting with 1 and a number starting with 0 will end up having the next second bit cancel out, so we should just look at the third bit.

这给出了下面的递归算法，从两组由他们MSB分区的数字，给出了答案：

This gives the following recursive algorithm that, starting with the two groups of numbers partitioned by their MSB, gives the answer:

• 在给定组1和组0和位索引​​i：
  • 如果该位索引等于比特数，返回（独特）数的异或中的1组，并在组0的（唯一的）数目
  • 在建设组11，10，01，00从这些群体。
  • 如果组11和00组的非空，递归地发现这两个群体的最大XOR i位开始+ 1。
  • 如果组10和01组的非空，递归地发现这两个群体的最大XOR，i位开始+ 1。
  • 如果上述任何一种配对​​是有可能的，然后返回由递推找到的最大的一对。
  • 否则，所有的数字都必须在我的位置相同的位，所以通过观察位返回找到的最大对我+ 1组1和0。
  • Given group 1 and group 0 and a bit index i:
    • If the bit index is equal to the number of bits, return the XOR of the (unique) number in the 1 group and the (unique) number in the 0 group.
    • Construct groups 11, 10, 01, and 00 from those groups.
    • If group 11 and group 00 are nonempty, recursively find the maximum XOR of those two groups starting at bit i + 1.
    • If group 10 and group 01 are nonempty, recursively find the maximum XOR of those two groups, starting at bit i + 1.
    • If either of the above pairings was possible, then return the maximum pair found by the recursion.
    • Otherwise, all of the numbers must have the same bit in position i, so return the maximum pair found by looking at bit i + 1 on groups 1 and 0.

    要开始的算法，实际上你可以从最初的组号码只分成两组 - 有MSB 1号和电话号码与MSB 0。然后，断火上述算法的递归调用与两组数字。

    To start off the algorithm, you can actually just partition the numbers from the initial group into two groups - numbers with MSB 1 and numbers with MSB 0. You then fire off a recursive call to the above algorithm with the two groups of numbers.

    作为一个例子，考虑数5 1 4 3 0 2。这些已经重新presentations

    As an example, consider the numbers 5 1 4 3 0 2. These have representations

    101  001  100   011   000   010
    

    我们首先将其拆分成1组和0组：

    We begin by splitting them into the 1 group and the 0 group:

    101  100
    001  011  000  010
    

    现在，我们运用上述算法。我们它分成组11，10，01，00：

    Now, we apply the above algorithm. We split this into groups 11, 10, 01, and 00:

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

    现在，我们不能配对任何11元与00元，所以我们只递归在10和01组。这意味着我们构建了100，101，010，和011组：

    Now, we can't pair any 11 elements with 00 elements, so we just recurse on the 10 and 01 groups. This means we construct the 100, 101, 010, and 011 groups:

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

    现在，我们是到水桶与他们只有一个元素，我们就可以检查对101和010（可提供111）以及100和011（可提供111）。无论是选择在这里工作，所以我们得到了最佳的答案是7。

    Now that we're down to buckets with just one element in them, we can just check the pairs 101 and 010 (which gives 111) and 100 and 011 (which gives 111). Either option works here, so we get that the optimal answer is 7.

    让我们想想这个算法的运行时间。注意，最大递归深度为O（LG U），因为只有为O（log U）中的数字位。在树中的每个级中，每个号码出现在正好一个递归调用，并且每个递归调用的确实工作成比例的数，在0和1基团的总数，因为我们需要通过它们的位来分发它们。因此，有O（登录U）在递归树级别，每个级别不为O（n）的工作，给人o一个总的工作（N日志U）。

    Let's think about the running time of this algorithm. Notice that the maximum recursion depth is O(lg U), since there are only O(log U) bits in the numbers. At each level in the tree, each number appears in exactly one recursive call, and each of the recursive calls does work proportional to the total number of numbers in the 0 and 1 groups, because we need to distribute them by their bits. Consequently, there are O(log U) levels in the recursion tree, and each level does O(n) work, giving a total work of O(n log U).

    希望这有助于！这是一个真棒的问题！

    Hope this helps! This was an awesome problem!

    这篇关于其异或为最大的数组两个元素的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！