数组中两个数的最大异或值 图解题解

这道题到底在问什么

输入

nums = [3,10,5,25,2,8]

输出

28(5 XOR 25)

输入

nums = [3,5,6]

输出

6(3 XOR 5)

最优解：一步一步想明白

1. 3记住「高位优先、能相反就相反」:异或的高位拉开差距最划算,所以每个数都尽量去匹配一个高位与它相反的数。下面先建树、再查询,逐帧套它。
2. 4插入 3:第 1 位 0 → 节点 0
3. 5插入 3:第 2 位 1 → 节点 01
4. 6插入 3:第 3 位 1 → 节点 011
5. 7插入 5:第 1 位 1 → 节点 1
6. 8插入 5:第 2 位 0 → 节点 10
7. 9插入 5:第 3 位 1 → 节点 101
8. 10插入 6:第 1 位 1 → 节点 1
9. 11插入 6:第 2 位 1 → 节点 11
10. 12插入 6:第 3 位 0 → 节点 110
11. 13字典树建好:3 个数各走出一条根到叶的路径
12. 14查询 3:第 1 位想走 1 → 成功,这位记 1
13. 15查询 3:第 2 位想走 0 → 成功,这位记 1
14. 16查询 3:第 3 位想走 0 → 失败,这位记 0
15. 17数 3 的最佳异或 = 6;ans = 6
16. 18查询 5:第 1 位想走 0 → 成功,这位记 1
17. 19查询 5:第 2 位想走 1 → 成功,这位记 1
18. 20查询 5:第 3 位想走 0 → 失败,这位记 0
19. 21数 5 的最佳异或 = 6;ans = 6
20. 22查询 6:第 1 位想走 0 → 成功,这位记 1
21. 23查询 6:第 2 位想走 0 → 失败,这位记 0
22. 24查询 6:第 3 位想走 1 → 成功,这位记 1
23. 25数 6 的最佳异或 = 5;ans = 6
24. 26答案:最大异或 = 6

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

from typing import List
class Solution:
    def findMaximumXOR(self, nums: List[int]) -> int:
        root = {}
        for x in nums:
            node = root
            for b in range(31, -1, -1):
                bit = (x >> b) & 1
                node = node.setdefault(bit, {})
        ans = 0
        for x in nums:
            node = root
            cur = 0
            for b in range(31, -1, -1):
                bit = (x >> b) & 1
                want = bit ^ 1
                if want in node:
                    cur |= 1 << b
                    node = node[want]
                else:
                    node = node[bit]
            ans = max(ans, cur)
        return ans

#include <vector>
using namespace std;
class Solution {
    struct Node { int child[2] = {-1, -1}; };
public:
    int findMaximumXOR(vector<int>& nums) {
        vector<Node> trie(1);
        for (int x : nums) {
            int p = 0;
            for (int b = 31; b >= 0; --b) {
                int bit = (x >> b) & 1;
                if (trie[p].child[bit] == -1) { trie[p].child[bit] = trie.size(); trie.push_back(Node()); }
                p = trie[p].child[bit];
            }
        }
        int ans = 0;
        for (int x : nums) {
            int p = 0, cur = 0;
            for (int b = 31; b >= 0; --b) {
                int bit = (x >> b) & 1, want = bit ^ 1;
                if (trie[p].child[want] != -1) { cur |= 1 << b; p = trie[p].child[want]; }
                else p = trie[p].child[bit];
            }
            ans = max(ans, cur);
        }
        return ans;
    }
};

import java.util.*;
class Solution {
    static class Node { Node[] child = new Node[2]; }
    public int findMaximumXOR(int[] nums) {
        Node root = new Node();
        for (int x : nums) {
            Node p = root;
            for (int b = 31; b >= 0; b--) {
                int bit = (x >>> b) & 1;
                if (p.child[bit] == null) p.child[bit] = new Node();
                p = p.child[bit];
            }
        }
        int ans = 0;
        for (int x : nums) {
            Node p = root;
            int cur = 0;
            for (int b = 31; b >= 0; b--) {
                int bit = (x >>> b) & 1, want = bit ^ 1;
                if (p.child[want] != null) { cur |= 1 << b; p = p.child[want]; }
                else p = p.child[bit];
            }
            ans = Math.max(ans, cur);
        }
        return ans;
    }
}

复杂度

面试官可能追问