【LeetCode】数组中两个数的最大异或值 Java 题解

关注

发布于: 2021 年 05 月 16 日

题目描述

给你一个整数数组 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.

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/maximum-xor-of-two-numbers-in-an-array著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

思路分析

这个题目题意简单明了，容易理解。通过暴力法，可以枚举得到结果。
比较好的解法是参考官方题解解法，采用字典树的做法，提升算法的效率。

AC 代码

暴力解法

    public int findMaximumXOR(int[] nums) {        int ans = 0;        int n = nums.length;        for (int i = 0; i < n - 1; i++) {            for (int j = i + 1; j < n; j++) {                ans = Math.max(ans, nums[i] ^ nums[j]);            }        }
        return ans;    }

复制代码

字典树解法

class Solution {    // 字典树的根节点    Trie root = new Trie();    // 最高位的二进制位编号为 30    static final int HIGH_BIT = 30;
    public int findMaximumXOR(int[] nums) {        int n = nums.length;        int ans = 0;        for (int i = 1; i < n; ++i) {            // 将 nums[i-1] 放入字典树，此时 nums[0 .. i-1] 都在字典树中            add(nums[i - 1]);            // 将 nums[i] 看作 ai，找出最大的 x 更新答案            ans = Math.max(ans, check(nums[i]));        }        return ans;    }
    public void add(int num) {        Trie cur = root;        for (int k = HIGH_BIT; k >= 0; --k) {            int bit = (num >> k) & 1;            if (bit == 0) {                if (cur.left == null) {                    cur.left = new Trie();                }                cur = cur.left;            }            else {                if (cur.right == null) {                    cur.right = new Trie();                }                cur = cur.right;            }        }    }
    public int check(int num) {        Trie cur = root;        int x = 0;        for (int k = HIGH_BIT; k >= 0; --k) {            int bit = (num >> k) & 1;            if (bit == 0) {                // a_i 的第 k 个二进制位为 0，应当往表示 1 的子节点 right 走                if (cur.right != null) {                    cur = cur.right;                    x = x * 2 + 1;                } else {                    cur = cur.left;                    x = x * 2;                }            } else {                // a_i 的第 k 个二进制位为 1，应当往表示 0 的子节点 left 走                if (cur.left != null) {                    cur = cur.left;                    x = x * 2 + 1;                } else {                    cur = cur.right;                    x = x * 2;                }            }        }        return x;    }}
class Trie {    // 左子树指向表示 0 的子节点    Trie left = null;    // 右子树指向表示 1 的子节点    Trie right = null;}

复制代码

总结

暴力枚举方法的时间复杂度是 O(n * n), 空间复杂度是 O(1)
字典树的解法时间复杂度是 O(n log C), 空间复杂度是 O(n log C)
坚持每日一题，加油！

发布于: 2021 年 05 月 16 日阅读数: 10

原文链接:【http://xie.infoq.cn/article/9cc3cd5cfc194779a8dfa6a02】。文章转载请联系作者。

HQ数字卡

关注

还未添加个人签名 2019.09.29 加入

LeetCode,略懂后端的RD

发布

暂无评论

创作场景

【LeetCode】数组中两个数的最大异或值 Java 题解

题目描述

思路分析

AC 代码

总结

HQ数字卡

评论