421. 數組中兩個數的最大異或值

思路

1. 哈希表

1. 接下來要嘗試能不能合成出 $10000$，我們用哈希表將出現過的數字紀錄下來。
   並在遍歷時判斷目標數字是否曾出現在哈希表中，可以合成出來，那麼最後答案的最高位就是$1$。

2. 再去嘗試第三位，當前目標數字：$10000\to11000$，重複步驟1，依舊可以成功合成。

3. 第二位發現無法合成出目標數字 $11100$，$\text{\small{\orange{因此最後答案的第二位是}}}\orange{0}$

4. 嘗試合成第一位，目標數字：$11000\to11010$，可以合成。

5. 來到最後一位，目標數字：$11010\to11011$，可以合成。

因此最後的答案是$11011$。

程式碼

class Solution {
public:
    int findMaximumXOR(vector<int>& nums) {
        int res = 0;
        int mx = ranges::max(nums);
        int high = mx == 0 ? 0 : __lg(mx); // 最高位出現的位置

        // target: 想要合成出的目標
        // i: 當前想合成出的位置
        auto canMerge = [&](int target, int i) -> bool {
            unordered_map<int, bool> umap;
            for(int x : nums) {
                x = (x >> i) << i; // 清除位置 i 後面的 0 
                if(umap.contains(x ^ target)) { // 包含目標數字，可以合成出 target
                    return true;
                }
                umap[x] = true;
            }
            return false;
        };

        for(int i = high; i >= 0; i--) {
            int target = res | (1 << i);
            if(canMerge(target, i)) { // 這一位可以是 1
                res = target;
            }
        }
        return res;
    }
};

思路2. 前綴樹

前綴樹介紹

假如當前要配對的數字是 $a=99=01100011$，想讓結果數值大，得盡量讓前面位數跟配對的數字相異。
因此，把所有數丟到前綴樹中後，拿數字 $a$ 到前綴樹中去找。

• 第一位數 $0$，沒有 $1$ 的路可以走，因為非負。
• 第二位數 $1$，看有沒有 $0$ 的路可以走，有就前進。
• 第三位數 $1$，看有沒有 $0$ 的路可以走，有就前進。
• 第四位數 $0$，看有沒有 $1$ 的路可以走，有就前進。
• …

注意事項

1. 不需要 $\text{pass}$ 以及 $\text{end}$ 變數，因為只需判斷路存不存在。
2. 開始建立前綴樹之前，先找出最大值最高位的 $1$ 在哪個位置，並以它作為最高位
   • 這樣做能省去在找配對數字時，前導 $0$ 的無效比較。
3. 假如沒有自己想要走的路，那就只能走跟自己位元相同的路。
   • 兩條路中必定存在一條路可走，因為當初加入數字時，一定會從最高位連到最低位。

1. 類別實作

 struct TrieNode {
    array<TrieNode*, 2> nexts;
    TrieNode() : nexts{nullptr} {}
};
class Trie {
private:
    int high;
    TrieNode* root;
public:
    Trie() {
        root = new TrieNode();
        high = 31;
    }
    void insert(vector<int>& nums) {
        int mx = ranges::max(nums);
        high = mx == 0 ? 0 : bit_width((unsigned int)mx) - 1; // 找到最高位的 1 所在的位置
        for(int x : nums) {
            TrieNode* cur = root;
            for(int i = high; i >= 0; i--) {
                int path = (x >> i) & 1;
                if(cur->nexts[path] == nullptr) {
                    cur->nexts[path] = new TrieNode();
                }
                cur = cur->nexts[path];
            }
        }
    }
    int maxXorValue(int x) {
        int res = 0;
        TrieNode* cur = root;
        for(int i = high; i >= 0; i--) {
            int path = (x >> i) & 1;
            int want = path ^ 1;
            if(cur->nexts[want] == nullptr) { // 沒有想要的路可走，只能走另一條
                want ^= 1;
            }
            res |= (path ^ want) << i; // 跟想要走的路是否相同? 如果不同，那麼 xor 的數值就會是 1
            cur = cur->nexts[want];
            // 不可能無路可走，因為加入時，後綴的 0 都有被加入。
        }
        return res;
    }
};
class Solution {
public:
    int findMaximumXOR(vector<int>& nums) {
        Trie trie;
        trie.insert(nums);

        int res = 0;
        for(int x : nums) {
            res = max(res, trie.maxXorValue(x));
        }
        return res;
    }
};

2.靜態數組實作

class Solution {
private:
    int cnt;
    int high = 31;
    int trie[3000001][2]; // 每個位置只有 0, 1 兩條路可走
    
    void insert(vector<int>& nums) {
        int mx = ranges::max(nums);
        high = mx == 0 ? 0 : (int)bit_width((unsigned int)mx) - 1; // 相當於 __lg(mx)
        for(int x : nums) {
            int cur = 1;
            for(int i = high; i >= 0; i--) {
                int path = (x >> i) & 1;
                if(trie[cur][path] == 0) {
                    trie[cur][path] = ++cnt;
                }
                cur = trie[cur][path];
            }
        }
    }

    int maxXorValue(int num) {
        int res = 0;
        int cur = 1;
        for(int i = high; i >= 0; i--) {
            int path = (num >> i) & 1;
            int want = path ^ 1;
            if(trie[cur][want] == 0) {
                want ^= 1;
            }
            cur = trie[cur][want];
            res |= (path ^ want) << i;
        }
        return res;
    }
public:
    int findMaximumXOR(vector<int>& nums) {
        cnt = 1;
        insert(nums);
        int res = 0;
        for(int x : nums) {
            res = max(res, maxXorValue(x));
        }
        return res;
    }
};

複雜度分析

• 時間複雜度：$O(n\log{\max(nums)})$
• 空間複雜度：$O(n)$