題目網址：https://leetcode.cn/problems/maximum-xor-of-two-numbers-in-an-array/

題意：給一整數 array nums, 返回 nums[i] XOR nums[j] 的最大值, 其中 0 ≤ i ≤ j < n。

進階：設計 $O(n)$ time 的演算法。

Solution：

想法：利用 Greedy + Trie

  • Greedy：若今天有一數 x = 5, 其 binary 形式為 0101

    • 若跟其 bit 完全相反的 1010 存在, 則 XOR 值最大
    • 若 1010 不存在, 我們也希望能挑選最左 bit = 1 (因為此時 5 的最左 bit = 0)的數, 並將最左 bit = 0 的數給剔除掉, 然後往下一個 bit 重複此步驟
    • 透過逐步篩選, 最後挑出所有數中 XOR 值最大的數

  • 首先, 將所有 num 的 binary 形式(由左至右) insert 到 trie 中

    e.g. num = 4 則 insert 到 trie 中會是下圖的樣子

  • 然後根據每一個 num 去找其 XOR 最大的數, 每次需花費 $O(32*2)$

class TrieNode {
public:
    TrieNode* children[2] = {nullptr};
};

class Trie {
public:
    Trie() : root(new TrieNode()) {}

    // 將 num 的 binary bit, 由左至右一個一個 insert 到 trie 中
    void insert(int& num){
        TrieNode *p = root;
        for (int i = 31; i >= 0; --i) {
            const int bit = (num >> i) & 1;
            if (!p->children[bit]) {
                p->children[bit] = new TrieNode();
            }
            p = p->children[bit];
        }
    }

    int search(vector<int>& nums){
        int res = 0;
        for (const auto& num : nums) {
            int cur = 0;
            TrieNode *p = root;

            for (int i = 31; i >= 0; --i) {
                const int bit = (num >> i) & 1; // 當前的 bit

                // 若 flip_bit 存在
                if (p->children[1 - bit]) {
                    // 2 * cur 是因為每做一個 bit 就要往左一位
                    // + 1 是因為 flip_bit 存在, 當前 bit XOR 完必為 1
                    cur = 2 * cur + 1;
                    p = p->children[1 - bit];
                } else { // 若 flip_bit 不存在
                    // 因為 flip_bit 不存在, 當前 bit XOR 完必為 0
                    cur *= 2;
                    p = p->children[bit];
                }
            }

            res = max(res, cur);
        }

        return res;
    }

private:
    TrieNode *root;
};

class Solution {
public:
    int findMaximumXOR(vector<int>& nums) {
        Trie trie;
        for (const auto& num : nums) {
            trie.insert(num);
        }
        return trie.search(nums);
    }
};
  • time：$O(n)$ ➔ $O(64n)$
    • search 一個 32-bit 的數, 每一個 bit 最多需 $O(2)$, 因為若 flip bit 不存在, 則要拜訪另一個
  • space：$O(n)$ ➔ $O(64n)$
    • 每 insert 一個數(32 bit), trie 最多產生 32 個 node, 而每個 node 又有 2 個 child