6

配列の 3 つの要素の最大 xor 値を見つけるアルゴリズムを知りたいです。配列の 2 つの要素の最大 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 = 配列の最大値

4

3 に答える 3

0

3 つのネストされたループの場合:

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）を実行しますが、より最適化されたアプローチ-同じ組み合わせを複数回テストせず、要素自体をテストせず、多少最適化された評価（すべての可能な3番目の要素に対して最初の2つの要素を1回xorします）

実行される 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 に答える