数组中两个数的最大异或值

这道题使用 Trie 前缀树存储数组中每个数。遍历数组中的数，从高位遍历一个数的每一位，将其存入 Trie 树。遍历每个数时，在 Trie 里面查询与它异或最大的数，方法是：遍历这个数的每一位，在 Trie 里面尽量选择与这一位相反的路径，到达叶节点时，这个路径代表的数就是与当前这个数异或最大的数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
 public:
  // 用二维 vector 模拟 Trie 树
  vector<vector<int>> s;
  // s[当前节点编号][当前节点第几个孩子] = 孩子节点编号，「当前节点第几个孩子」里面蕴含了信息，本题有两个孩子，0 和 1 代表这一位是 0 还是 1
  void insert(int x) {
    int p = 0;
    for (int i = 30; i >= 0; i--) {
      // 取出当前位
      int u = x >> i & 1;
      // 如果这一位不在 Trie 里，new 一个节点，然后让当前节点指向它
      if (!s[p][u]) s[p][u] = s.size(), s.push_back({0, 0});
      p = s[p][u];
    }
  }
  int query(int x) {
    int p = 0;
    int res = 0;
    for (int i = 30; i >= 0; i--) {
      int u = x >> i & 1;
      // 尽量选择与当前数这一位相反的路径
      if (s[p][!u])
        p = s[p][!u], res = res * 2 + !u;
      else
        p = s[p][u], res = res * 2 + u;
    }
    return res ^ x;
  }
  int findMaximumXOR(vector<int>& nums) {
    s.push_back({0, 0});
    int res = 0;
    for (auto x : nums) {
      res = max(res, query(x));
      insert(x);
    }
    return res;
  }
};