一、题目

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

进阶：你可以在 O(n) 的时间解决这个问题吗？

点击查看原题

二、思路

由于异或运算特性是0^1=1，求两两元素异或值最大，则尽可能结果高位都为1（两元素高位尽可能都一个为1另一个为0）。

1）暴力法

每个两个数都尝试一遍，使用两层for循环，找出最大值，时间复杂度为O(n).

2）字典树

对暴力法进行优化，即减少一层for循环。将每个元素的二进制看作字符串，先使用字典树对所有的元素进行记忆化（从二进制高位作为根节点进行记忆，保证每个不同的元素存在于不同的叶子节点）。然后遍历一遍，找出两两异或值最大的结果。

3）哈希表

这个和上面的两个方法不太一样，使用一个Set类型进行记录最高位到第i位的值，由于需要尽可能让高位的异或结果为1，使用一个变量ans进行记录最高位到第i位的最大异或值，然后不断进行查询。（很抽象，手推代码自己体会）

三、代码

字典树

class Solution {
    public int findMaximumXOR(int[] nums) {
        Trie root = new Trie();
        for (int num : nums) {    // 先存入字典树
            insert(root, num);
        }
        int ans = 0;
        for (int num : nums) {    // 对每个元素都找能匹配的最大
            ans = Math.max(ans, check(root, num));
        }
        return ans;
    }
    // 插入字典树
    public void insert(Trie root, int num) {
        for (int i = 30; i >= 0; i--) {
            int bitValue = (num >> i) & 1;
            if (bitValue == 1) {
                if (root.right == null) {
                    root.right = new Trie();
                }
                root = root.right;
            } else {
                if (root.left == null) {
                    root.left = new Trie();
                }
                root = root.left;
            }
        }
    }
    // 找到与num值异或最大的结果
    public int check(Trie root, int num) {
        int ans = 0;
        for (int i = 30; i >= 0; i--) {
            int numBitValue = (num >> i) & 1;
            if (numBitValue == 1) {
                // 当num的第i+1位为1时，尽可能找同样位为0的数
                if (root.left != null) {
                    root = root.left;
                    ans = (ans << 1) + 1;
                } else {    // 找不到i+1位为0的数时，就往另一分支继续查询
                    root = root.right;
                    ans = (ans << 1);
                }
            } else {
                if (root.right != null) {
                    root = root.right;
                    ans = (ans << 1) + 1;
                } else {
                    root = root.left;
                    ans = (ans << 1);
                }
            }
        }
        return ans;
    }
}
class Trie {
    public Trie left;   //0
    public Trie right;   //1
}

时间复杂度为O(nlogC)，其中C为元素的二进制位数，空间复杂度位O(nlogC)。

哈希表

class Solution {
    public int findMaximumXOR(int[] nums) {
        int ans = 0;
        for (int i = 30; i >= 0; i--) {
            Set<Integer> memo = new HashSet();    // 每循环一次初始化一次
            for (int num : nums) {
                memo.add(num >> i);    // 记录每个元素最高位到i + 1位
            }
            int ansNext = (ans << 1) + 1;    // 假设i+1位能异或出1
            boolean findFlag = false;
            for (int num : nums) {
                // 由于ansNext是由两个元素异或而成的，假设两个元素之一是num高位部分，那么ansNext ^ (num >> i)就是另一个元素的高位部分
                if (memo.contains(ansNext ^ (num >> i))) {
                    findFlag = true;
                    break;
                }
            }
            // 上面这个循环找到元素就假设成立，找不到就假设失败
            if (findFlag) {
                ans = ansNext;
            } else {
                ans = ansNext - 1;
            }
        }
        return ans;
    }
}

时间复杂度为O(nlogC)，其中C为元素的二进制位数，空间复杂度位O(n)。

个人博客

421. 数组中两个数的最大异或值-每日一题