题目描述：
给你一个整数数组 nums ，返回 nums[i] XOR nums[j] 的最大运算结果，其中 0 ≤ i ≤ j < n 。
示例 1：
输入：nums = [3,10,5,25,2,8]
输出：28
解释：最大运算结果是 5 XOR 25 = 28.
示例 2：
输入：nums = [14,70,53,83,49,91,36,80,92,51,66,70]
输出：127
提示：
1 <= nums.length <= 2 * 1050 <= nums[i] <= 2^31 - 1
思路：
题目意思呢非常清晰，就是求一个数组中任意两个数的最大异或值。很明显，直接暴力两重for循环时间复杂度太高了。我们可以把数组中的每一个数字都看出一个31位的二进制序列，根据异或的特性，二进制位不同的数异或得1，也就是说，我们要想找到的异或对最大，那么我们就尽量让这两个数得二进制位都不一样，并且优先从高位考虑。
这里我们可以用字典树来存放数组中每一个数的二进制序列，对于每一个节点都有两个儿子节点，0或者1，假如在这个树里要找一个与x异或最大的数，我们先找与x二进制中最高位的数异或得1的数，换句话说就是找不一样的数呗，假如x的最高位是1，那么要想异或的答案最大，我们看看这个树里面有没有这个位上是0的数，如果有走到这个节点去继续找下一位。
用一个二维数组son[p][u]来模拟一个字典树，第一维表示字典树的节点，第二维表示每个节点的子节点。son[p][u]的值表示这个节点的儿子节点的编号。
代码：
#define _CRT_SECURE_NO_WARNINGS 1 const int N = 1e5 + 10, M = 31 * N;//每个元素都有31位二进制序列 int son[M][2], idx; class Solution { public: void insert(int x) { int p = 0; for (int i = 30; i >= 0; i--) { int u = x >> i & 1; if (!son[p][u])son[p][u] = ++idx;//更新节点编号 p = son[p][u];//找到儿子节点的编号 } } long long query(int x) { long long res = 0; int p = 0; for (int i = 30; i >= 0; i--) { int u = x >> i & 1; if (son[p][!u]) { res = res * 2 + 1;//在当前节点存在！u,说明这位异或得1 p = son[p][!u]; } else { res = res * 2;//在当前节点不存在！u,说明这位异或得0 p = son[p][u]; } } return res; } int findMaximumXOR(vector<int>& nums) { memset(son, 0, sizeof(son)); idx = 0; int ans = 0; for (auto it : nums) { insert(it); int res = query(it); ans = max(ans, res); } return ans; } };
注意
为什么是一边插入一边查询呢？
根据异或规则，a^b=c等价于b^a=c，所以，异或对的顺序不会影响答案。我们在插入x的时候，可以在x之前的数中找与x异或最大的值，后面的数插进去后也是同样的操作，这样一来，对于任意一个元素x,它都有机会跟任意一个元素异或，所以得到的ans一定包含最大答案。
