LeetCode_前缀树_贪心算法_中等_421.数组中两个数的最大异或值-蒲公英云

LeetCode_前缀树_贪心算法_中等_421.数组中两个数的最大异或值

1.题目

给你一个整数数组 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 * 105
0 <= nums[i] <= 231 - 1

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/maximum-xor-of-two-numbers-in-an-array

2.思路

（1）暴力穷举法
暴力穷举法比较容易想到，即使用 2 层 for 循环来枚举所有 nums[i] XOR nums[j] 的结果，并且在枚举过程中使用变量 res 来记录最大值。不过该方法的时间复杂度较高，为 O(n2)，在 LeetCode 中提交时会出现“超出时间限制”的提示！

（2）前缀树 & 贪心
思路参考该 LeetCode 用户题解。

3.代码实现（Java）

//思路1————暴力穷举法
class Solution {
    public int findMaximumXOR(int[] nums) {
        int length = nums.length;
        int res = Integer.MIN_VALUE;
        for (int i = 0; i < length; i++) {
            for (int j = i; j < length; j++) {
                res = Math.max(res, nums[i] ^ nums[j]);
            }
        }
        return res;
    }
}
//思路2————前缀树 & 贪心
class Solution {
    class Node {
        Node[] ns = new Node[2];
    }
    //初始化字典树的根节点
    Node root = new Node();
    //将 x 添加到字典树中
    public void add(int x) {
        Node p = root;
        for (int i = 31; i >= 0; i--) {
            //获取 x 的二进制表示的第 i 位(从左往右，依次是第 31 位、30位、...、0位)
            int u = (x >> i) & 1;
            if (p.ns[u] == null) {
                p.ns[u] = new Node();
            }
            p = p.ns[u];
        }
    }
    //获取字典树中与 x 的异或结果最大的数
    public int getVal(int x) {
        int res = 0;
        Node p = root;
        /*
            采用如下贪心策略：对于 x 而言，可以从其二进制表示中的最高位开始往低位找，
            尽量让每一位的异或结果为 1，这样找到的 res 与 x 的异或结果才是最大的。
        */
        for (int i = 31; i >= 0; i--) {
            //获取 x 的二进制表示的第 i 位
            int a = (x >> i) & 1;
            //获取 x 的二进制表示的第 i 位的相反位
            int b = 1 - a;
            if (p.ns[b] != null) {
                res |= (b << i);
                p = p.ns[b];
            } else {
                res |= (a << i);
                p = p.ns[a];
            }
        }
        return res;
    }
    public int findMaximumXOR(int[] nums) {
        int res = 0;
        for (int num : nums) {
            add(num);
            int j = getVal(num);
            res = Math.max(res, num ^ j);
        }
        return res;
    }
}