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

Question

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

有一种简单的方法——只需选择每个元素并与其他元素进行异或，然后比较结果即可找到该对。

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

Answer 1

这可以使用 Trie 以 O(NlogN) 时间复杂度解决。

• 构造一个特里树。对于每个整数键，trie 的每个节点将保存从最高有效位开始的每一位（0 或 1）。
• 现在对于 arr[0, 1, ..... N] 的每个 arr[i] 元素
  • 执行查询以检索 arr[i] 可能的最大异或值。我们知道不同类型的位（0 ^ 1 或 1 ^ 0）的异或总是1。因此，在查询每个位时，尝试遍历持有相反位的节点。这将使特定位 1 导致异或值最大化。如果不存在位相反的节点，才遍历同位节点。
  • 查询后，将arr[i]插入trie中。
  • 对于每个元素，跟踪可能的最大异或值。
  • 在遍历每个节点的过程中，构建要最大化异或的另一个密钥。

对于 N 元素，我们需要为每个元素进行一次查询 (O(logN)) 和一次插入 (O(logN))。所以总体时间复杂度是O(NlogN)。

您可以在此线程中找到有关其工作原理的精美图解说明。

下面是上述算法的 C++ 实现：

const static int SIZE = 2;
const static int MSB = 30;
class trie {
private:
    struct trieNode {
        trieNode* children[SIZE];
        trieNode() {
            for(int i = 0; i < SIZE; ++i) {
                children[i] = nullptr;
            }
        }
        ~trieNode() {
            for(int i = 0; i < SIZE; ++i) {
                delete children[i];
                children[i] = nullptr;
            }
        }
    };
    trieNode* root;
public:
    trie(): root(new trieNode()) {
    }
    ~trie() {
        delete root;
        root = nullptr;
    }

    void insert(int key) {
        trieNode* pCrawl = root;
        for(int i = MSB; i >= 0; --i) {
            bool bit = (bool)(key & (1 << i));
            if(!pCrawl->children[bit]) {
                pCrawl->children[bit] = new trieNode();
            }
            pCrawl = pCrawl->children[bit];
        }
    }

    int query(int key, int& otherKey) {
        int Xor = 0;
        trieNode *pCrawl = root;
        for(int i = MSB; i >= 0; --i) {
            bool bit = (bool)(key & (1 << i));
            if(pCrawl->children[!bit]) {
                pCrawl = pCrawl->children[!bit];
                Xor |= (1 << i);
                if(!bit) {
                    otherKey |= (1 << i); 
                } else {
                    otherKey &= ~(1 << i);
                }
            } else {
                if(bit) {
                    otherKey |= (1 << i); 
                } else {
                    otherKey &= ~(1 << i);
                }
                pCrawl = pCrawl->children[bit];
            }
        }
        return Xor;
    }
};

pair<int, int> findMaximumXorElements(vector<int>& arr) {
    int n = arr.size();
    int maxXor = 0;
    pair<int, int> result; 
    if(n < 2) return result;
    trie* Trie = new trie();
    Trie->insert(0); // insert 0 initially otherwise first query won't find node to traverse
    for(int i = 0; i < n; i++) {
        int elem = 0;
        int curr = Trie->query(arr[i], elem);
        if(curr > maxXor) {
            maxXor = curr;
            result = {arr[i], elem};
        }
        Trie->insert(arr[i]);
    }
    delete Trie;
    return result;
}

Answer 2

忽略符号位，其中一个值必须是具有最高有效位设置的值之一。 除非所有值都设置了该位，在这种情况下，您将转到未在所有值中设置的下一个最高有效位。因此，您可以通过查看 HSB 来减少第一个值的可能性。例如，如果可能性是

0x100000
0x100ABC
0x001ABC
0x000ABC

最大对的第一个值必须是 0x100000 或 0x10ABCD。

@内部服务器错误我认为最小不一定是正确的。我没有减少第二个值的好主意。只是可能的第一个值列表中不的任何值。在我的示例中，为 0x001ABC 或 0x000ABC。

Answer 3

一个非常有趣的问题！
这是我的想法：

• 首先使用二叉树从所有数字构建一棵二叉树
  表示并首先将它们排序到树中最高有效位
  （添加前导零以匹配最长的数字）。完成每条路径后
  从根到任意叶子都代表原来的一个数字
  放。
• 设 a 和 b 为指向树节点的指针，并在根处初始化它们。
• 现在将 a 和 b 沿树向下移动，尝试在每一步使用相反的边，即，如果 a 向下移动 0 边，则 b 向下移动 1 边，除非不可能。

如果 a 和 b 到达叶子，则 应该指向具有“很少”相同位的两个数字。

我刚刚提出这个算法，不知道它是否正确或如何证明它。然而它应该在 O(n) 运行时间内。

Answer 4

创建一个递归函数，将两个整数列表 A 和 B 作为参数。作为其返回值，它返回两个整数，一个来自 A，一个来自 B，这使得两者的 XOR 最大化。如果所有整数均为 0，则返回 (0,0)。否则，该函数会进行一些处理并递归调用自身两次，但使用较小的整数。在其中一个递归调用中，它考虑从列表 A 中取出一个整数，为位 k 提供 1，而在另一个调用中，它考虑从列表 B 中取出一个整数，为位 k 提供 1。

我现在没有时间填写详细信息，但也许这足以看到答案？另外，我不确定运行时间是否会比 N^2 更好，但可能会。

Answer 5

我们可以在 O(n) 时间内找到最大数，然后循环遍历数组，对每个元素进行异或。假设异或运算成本为 O(1)，我们可以在 O(n) 时间内找到两个数字的最大异或。

Answer 6

我想我有一个 O(n lg U) 算法，其中 U 是最大的数字。这个想法与user949300类似，但有更多细节。

直觉如下。当您将两个数字异或在一起时，为了获得最大值，您希望在尽可能最高的位置有一个 1，然后是具有 1 的配对在这个位置，您希望与下一个可能的最高位置处的 1 进行配对，依此类推。

因此算法如下。首先找到数字中任意位置的最高 1 位（您可以通过执行 O(lg U) 在 O(n lg U) 时间内完成此操作code> 对每个 n 数字起作用）。现在，将数组分成两部分 - 一个是该位中具有 1 的数字，另一个是该位中具有 0 的数字。任何最佳解决方案都必须将第一个位置带有 1 的数字与该位置带有 0 的数字组合起来，因为这样会出现 1 > 尽可能高一点。任何其他配对都有 0。

现在，我们希望递归地从 1 和 0 组中找到 1 最高的数字配对。为此，请将这两组中的它们分为四组：

• 以 11 开头的数字
• 以 10
• 开头的数字 以 01
• 开头的数字与 00

如果 11 和 00 组或 10 和 01 中有任何数字 组，他们的异或将是理想的（以 11 开头）。因此，如果这些组对中的任何一个不为空，则递归地计算这些组中的理想解决方案，然后返回这些子问题解决方案中的最大值。否则，如果两组都是空的，则意味着所有数字的第二个位置必须具有相同的数字。因此，以 1 开头的数字和以 0 开头的数字的最佳 XOR 最终会抵消下一个第二位，因此我们应该只看第三个位少量。

这给出了以下递归算法，该算法从按 MSB 划分的两组数字开始给出答案：

• 给定组 1 和组 0 以及位索引 我：
  • 如果位索引等于位数，则返回 1 组中的（唯一）数字与 0 组中的（唯一）数字的 XOR > 小组。
  • 从这些组中构造组 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记录U）。

希望这有帮助！这是一个很棒的问题！