题目

题目来源：力扣（LeetCode）

给定一个整数数组 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 = [0]
输出：0

示例 3：

输入：nums = [2,4]
输出：6

示例 4：

输入：nums = [8,10,2]
输出：10

示例 5：

输入：nums = [14,70,53,83,49,91,36,80,92,51,66,70]
输出：127

思路分析

  1. 在一个数组中求两个数的异或最大值，需要考虑以下两点：
    • 大的数异或后带来的增益较大，所以优先考虑大的数进行异或，也就是先考虑高位。
    • 只有当两个二进制位不同，二进制位才会为1，所以，我们尽量找到两个很多位都不同的数进行异或。
  2. 构建前缀树：将所有的数都插入前缀树中。与普通前缀树不同，这里是根据一个数的二进制位来插入，普通前缀树是根据单词中的字符来插入。还有一点需要注意的是，我们优先考虑高位，所以是从高位到低位进行插入
  3. 对于 nums 中的每个数 num ，都到前缀树中去搜索num最大异或的那个数，然后计算最大异或值，最后，从这些异或值中挑出最大的一个就是要的答案。
  1. /**
  2.  * @param {number[]} nums
  3.  * @return {number}
  4.  */
  5. var findMaximumXOR = function (nums) {
  6.   // 前缀树 先将每一个树的31位二进制位存入到前缀树中
  7.   let root = {};
  8.   for (let num of nums) {
  9.     let cur = root;
  10.     let bit = 0; // 减少空间
  11.     for (let i = 30; i >= 0; i--) { // JS是31位数，所以右移30位
  12.       // 数据是从高位开始存储(后面高位亦或取1，结果肯定是最大的)
  13.       bit = (num >> i) & 1;
  14.       if (!cur[bit]) cur[bit] = {};
  15.       cur = cur[bit];
  16.     }
  17.   }
  18.   // 时间复杂度 O(N) 因为每个数据在前缀树中查找一次就能得到它与其他数xor的最大结果
  19.   // 此处准确时间复杂度应该是 O(31N)
  20.   let ans = 0;
  21.   for (let num of nums) {
  22.     let cur = root;
  23.     let res = 0;
  24.     for (let i = 30; i >= 0; i--) {
  25.       let bit = (num >> i) & 1;
  26.       if (cur[1] && (1 ^ bit == 1)) {
  27.         res = (res << 1) + 1; // 有1取1
  28.         cur = cur[1];
  29.       } else if (cur[0] && (0 ^ bit == 1)) {
  30.         res = (res << 1) + 1; // 有1取1
  31.         cur = cur[0];
  32.       } else { // else 说明不是两个都有的，取一个有的就行
  33.         res = res << 1;
  34.         cur = cur[bit];
  35.       }
  36.     }
  37.     // 每次计算二进制算一次值
  38.     if (res > ans) ans = res;
  39.   }
  40.   return ans;
  41. };