数组中的三个元素,其xor是最大的

Question

我想知道一个算法来找出数组中三个元素的最大xor值.我已经阅读了关于数组中两个元素的最大xor但是无法理解如何应用它来查找数组的3个元素的XOR的最大值.有人能指出一个暗示吗？

所需的复杂度:小于O(N ^ 3)其中N是数组中元素的数量.

例:

A = [1,2,3,4]

所有可能的三胞胎: -

1 ^ 2 ^ 3 = 0
1 ^ 2 ^ 4 = 7
1 ^ 3 ^ 4 = 6
2 ^ 3 ^ 4 = 5

因此,最大XOR值为7.

编辑:

我想到了一个复杂度为O(N ^ 2*log(MAX))的解决方案,它解决了我的目的:D.

MAX =阵列中的最大值

Answer 1

好吧,我找到了一个复杂度为O(N ^ 2*log(MAX))的解决方案,其中MAX是数组中的最大值.

在阵列A上有3个元素X,Y,Z.

其中X = A [i],Y = A [j],Z = A [k],i!= j!= k

我们想要(X ^ Y ^ Z)的最大值.

让我们假设W = X*Y.

然后我们想找到这样一个Z,它给出W ^ Z和Z!= X和Z!= Y的最大值

现在这已经减少到找到" XOR最大的两个元素 "的问题,这可以使用Trie对O(log(MAX))中的给定W进行.

Trie的解释:

我们假设W = 10001,这里W是二进制的.

现在我们知道1 ^ 0 = 1,0 ^ 0 = 0,1 ^ 1 = 0,因此我们可以得到W ^ Z的最大值是当Z是01110时,因为 W ^ Z将给出= 11111.

但是我们的数组中没有必要使用15或Base2(11111),所以我们会选择最好的选项.

因此,我们将根据它们的二进制表示创建数组的所有元素的Trie.

如果A = [1,2,7] ,则1 = 001,2 = 010,J = 111二进制.

那么Trie看起来像: -

                            Top
                           /   \
                          0     1
                         / \     \
                        0   1     1
                         \ /       \
                         1 0        1

现在让我们假设W = 7,并且我们想要找到Z使得 W ^ Z是最大的(当Z = 000时)然后我们将从Top开始并看看我们是否有分支导致0,因为7的第一位是1,然后我们将通过该分支,然后再看看我们是否在第2位有分支导致0,再次我们找到它,然后我们最后一次搜索分支导致0位在第3位但是我们找不到它,所以我们通过另一个分支,它给我们Z = 001.因此,最大W ^ Z将是7 ^ 1 = 6.现在,找到Z的复杂性将是Trie的最大高度,它将是log(MAX).

因此,我们有N*(N-1)/ 2个数W,并且对于每个W,我们可以找到W ^ Z的最大值,如果我们从W ^ Z的所有值中取最大值,我们将得到我们的答案.