题目描述

给你一个整数数组 nums ，返回 nums[i] XOR nums[j] 的最大运算结果，其中 0 ≤ i ≤ j < n 。

进阶：你可以在 O(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 <= nums.length <= 2 * 104
• 0 <= nums[i] <= 2^31 - 1

思路

前言

假设我们在数组中选择了元素 a_i 和 a_j （i ≠ j），使得它们达到最大的按位异或运算结果 x：

x = a_i ⊕ a_j ​

其中 ⊕ 表示按位异或运算。要想求出 x，一种简单的方法是使用二重循环枚举 i 和 j，但这样做的时间复杂度为 O(n^2)，会超出时间限制。
因此，我们需要寻求时间复杂度更低的做法。

根据按位异或运算的性质，x = a_i ⊕ a_j ​ 等价于 a_j = x ⊕ a_i 。我们可以根据这一变换，设计一种从高位到低位依次确定 x 二进制表示的每一位的方法，以此得到 x 的值。该方法的精髓在于：

由于数组中的元素都在 [0, 2^31) 的范围内，那么我们可以将每一个数表示为一个长度为 31 位的二进制数（如果不满 31 位，在最高位之前补上若干个前导 0 即可）；

这 31 个二进制位从低位到高位依次编号为 0, 1,⋯,30。我们从最高位第 30 个二进制位开始，依次确定 x 的每一位是 0 还是 1；

由于我们需要找出最大的 x，因此在枚举每一位时，我们先判断 x 的这一位是否能取到 1。如果能，我们取这一位为 1，否则我们取这一位为 0。

判断 x 的某一位是否能取到 1 这一步骤并不容易。

方法：字典树

我们可以将数组中的元素看成长度为 31 的字符串，字符串中只包含 0 和 1。如果我们将字符串放入字典树中，那么在字典树中查询一个字符串的过程，恰好就是从高位开始确定每一个二进制位的过程。字典树的具体逻辑以及实现可以参考字典树：208. 实现 Trie (前缀树)，这里我们只说明如何使用字典树解决本题。

根据 x = a_i ⊕ a_j ，我们枚举 a_i ，并将 a₀，a₁，…，a_i-1 作为 a_j 放入字典树中，希望找出使得 x 达到最大值的 a_j。

如何求出 x 呢？我们可以从字典树的根节点开始进行遍历，遍历的参照对象为 a_i。在遍历的过程中，我们根据 a_i 的第 x 个二进制位是 0 还是 1，确定我们应当走向哪个子节点以继续遍历。假设我们当前遍历到了第 k 个二进制位：

如果 a_i 的第 k 个二进制位为 0，那么我们应当往表示 1 的子节点走，这样 0⊕1=1，可以使得 x 的第 k 个二进制位为 1。如果不存在表示 1 的子节点，那么我们只能往表示 0 的子节点走，x 的第 k 个二进制位为 0；

如果 a_i 的第 k 个二进制位为 1，那么我们应当往表示 0 的子节点走，这样 1⊕0=1，可以使得 x 的第 k 个二进制位为 1。如果不存在表示 0 的子节点，那么我们只能往表示 1 的子节点走，x 的第 k 个二进制位为 0。

当遍历完所有的 31 个二进制位后，我们也就得到了 a_i 可以通过异或运算得到的最大 x=x。这样一来，如果我们枚举了所有的 a_i，也就得到了最终的答案。

Java代码

class Solution {
    class Trie {
        Trie[] children = new Trie[2];
    }
    
    Trie root = new Trie();                            // 创建一个空的字典树节点
    
    public int findMaximumXOR(int[] nums) {
        int res = 0;
        for (int i = 0; i < nums.length; i++) {
            add(nums[i]);                              // 向字典树中添加节点 nums[i]
            int val = getVal(nums[i]);                 // 获取当前元素 nums[i] 与 前'i-1'个数字进行异或运算的结果最大的那个数字
            res = Math.max(res, nums[i] ^ nums[j]);    // 如果这个值比现有的最大值大，就更新答案
        }
        return res;
    }

    public void add(int num) {                         // 向字典树中添加一个数字表示              
        Trie node = root;
        for (int i = 30; i >= 0; i--) {                // 这里取30是因为数字的取值范围为 0 ~ 2^31-1，即最大31位，需要 0-30来表示
            int bit = (num >> i) & 1;                  // (num >> i) & 1 的作用是得到数字 num 的二进制表示形式的第 i 位 的值
            if(node.children[bit] == null) {
                node.children[bit] = new Trie();       // 如果字典树中当前位置没“路”了，需要新建一个节点
            }
            node = node.children[bit];                 // 继续遍历
        }
    }

    public int getVal(int num) {                       // 获取当前字典树的元素中，与'num'进行异或运算的结果最大的那个元素
        Trie node = root;
        int res = 0;
        for(int i = 30; i >= 0; i--) {                 // 这里取30是因为数字的取值范围为 0 ~ 2^31-1，即最大31位，需要 0-30来表示
            int a = (num >> i) & 1;                    // (num >> i) & 1 的作用是得到数字 num 的二进制表示形式的第 i 位 的值
            int b = 1 - a;                             // 如果当前位是'0'，那我们希望下一步能走 1；如果当前位是'1'，那我们希望下一步能走 0
            if(node.children[b] != null) {             // 如果最高位是1，那么判断树的这个位置0是否存在，存在走0，不存在走1，反之同理
                node = node.children[b];
                res |= (b << i);
            } else {                                   
                node = node.children[a];
                res |= (a << i);                       // res |= (a << i) 的作用是获取我们希望得到的那个元素的第 i 位的值
            }
        }
        return res;
    }
}

复杂度分析

时间复杂度：O(n)
空间复杂度：O(n)