6

我想知道一种算法来找出数组的三个元素的最大异或值。我已经阅读了有关数组中两个元素的最大异或的信息，但无法理解如何将其应用于查找数组中 3 个元素的异或的最大值。有人可以指出一个提示吗？

所需复杂度：小于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 = 数组中的最大值

4

3 回答 3

6

好吧，我找到了一个复杂度为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完成。

特里的解释：

让我们假设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，7 = 111二进制。

然后 Trie 看起来像：-

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

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

因此，我们有N*(N-1)/2个W，对于每个W，我们可以找到W^Z的最大值，如果我们从W^Z的所有值中取最大值，我们就会得到答案。

于 2013-09-29T10:31:47.453 回答
0

使用三个嵌套循环：

int max2=0,max3=0;
for (int i=0;i<arr.size();i++)
    for (int j=0;j<arr.size();j++)
        for (int k=0;k<arr.size();k++)
        {
            if (arr[i]^arr[j]>max2) // for 2 elements
               max2 = arr[i]^arr[j];
            if (arr[i]^arr[j]^arr[k]>max3) // for 3 elements
               max3 = arr[i]^arr[j]^arr[k];
        }

int max = max2; // for both
if (max3>max2)
   max = max3;
于 2013-09-29T06:20:44.600 回答
0

以下将执行 O(N^3)，但采用更优化的方法 - 不多次测试相同的组合，不针对自身测试元素，并进行一些优化的评估（将前两个元素异或一次，用于所有可能的第三个元素）

执行的 Xor 操作数将为：n(n-1)(n-2)/6 + n(n-1)/2

不过，复杂度仍然是 n(n-1)(n-2)/6 ===> O(N^3)。

unsigned int maxXor3(unsigned int* element, int len)
{
    unsigned int max = 0;
    unsigned int xor2 = 0;
    unsigned int xor3 = 0;
    int j = k = 0;

    for (int i = 0 ; i < len ; i++)
    {
        for (j = i + 1 ; j < len ; j++)
        {
            xor2 = element[i] ^ element[j];
            for(k = j + 1; k < len; k++)
            {
                xor3 = xor2 ^ element[k];
                if (xor3 > max)
                    max = xor3;
            }
        }
    }
    return max;
}
于 2013-09-29T08:40:27.200 回答