LeetCode 421. 数组中两个数的最大异或值

2025-06-24 HGNULB 约 6 分钟

文章信息 7 个分类 4 个标签

分类

题目描述

✅ 421. 数组中两个数的最大异或值

题意分析

题目要在数组里挑出两个数，使它们的异或值最大，返回这个最大值本身而不是那对数字。异或是按位独立运算，两个数在某一位上不同则该位结果为 1、相同则为 0，所以「让异或值尽量大」就是「让尽量高的位取到 1」。

数字之间的大小关系在这里完全没用，10 和 100 谁大都不能预测它们跟别人异或的结果，这说明排序、双指针、二分这些基于数值序的手段全部失效，必须换到二进制位的视角上去看。

数组长度可达 $2 \times 10^5$，两两枚举是 $4 \times 10^{10}$ 次运算，必然超时；而元素上界约 $2^{31}$，位数只有 31，这个「位数远小于元素个数」的对比是很强的信号：应该把复杂度里的一个 n 换成位数。

边界上要注意：元素非负，最高位（符号位）恒为 0，检查第 30 位到第 0 位就够；数组中可能有重复元素，但题目允许取两个不同下标，重复值互相异或得 0 不影响最大值；数组至少有两个元素，所以不必处理单元素的退化情形。

解法：0-1 Trie + 高位贪心

核心思路

异或值的大小由最高不同位优先决定。对第 bit 位，若能让结果为 1，就一定优于该位为 0 的所有方案，因为 $2^{bit}$ 大于全部更低位权值之和。因此给定一个数 x，应从高位到低位尽量寻找与它当前位相反的数字。

0-1 Trie 将每个整数看成固定 31 位二进制串：左孩子代表 0，右孩子代表 1。树中一条从根向下的路径代表某个二进制前缀，孩子存在就等价于「已有数字中存在这个前缀」。

查询时维护的不变量是：当前 Trie 节点代表所有符合此前贪心选择的候选数。每一位优先进入相反位孩子；若存在，就把答案对应位置 1，否则只能进入同位孩子。高位选择一旦更优，任何低位都不可能反超，因此逐位贪心得到当前数的最大异或搭档。

按数组顺序先查询、后插入，可以保证搭档来自此前下标，避免与自身配对，并让每一对不同下标在较晚元素查询时被考虑。

解题步骤

建立根节点，先插入第一个数，确保查询时 Trie 非空。

从第二个数开始，按第 30 位到第 0 位查询最佳搭档。

当前位为 bit 时，优先走 bit ^ 1 的孩子；成功则将异或结果该位置 1。

用本次查询结果更新全局最大值，再把当前数插入 Trie。

遍历结束返回最大值。

例如 5 的低 5 位是 00101，25 是 11001。查询 25 时，最高有效位优先匹配到 5 的 0，随后继续按相反位选择，得到 11100，即 $5 XOR 25 = 28$。

代码实现

class Solution {
    private static class Node {
        Node[] children = new Node[2];
    }

    public int findMaximumXOR(int[] nums) {
        Node root = new Node();
        insert(root, nums[0]);

        int answer = 0;
        for (int i = 1; i < nums.length; i++) {
            answer = Math.max(answer, query(root, nums[i]));
            insert(root, nums[i]);
        }
        return answer;
    }

    private void insert(Node root, int num) {
        Node node = root;
        for (int bit = 30; bit >= 0; bit--) {
            int value = (num >>> bit) & 1;
            if (node.children[value] == null) {
                node.children[value] = new Node();
            }
            node = node.children[value];
        }
    }

    private int query(Node root, int num) {
        Node node = root;
        int value = 0;
        for (int bit = 30; bit >= 0; bit--) {
            int current = (num >>> bit) & 1;
            int wanted = current ^ 1;
            if (node.children[wanted] != null) {
                value |= 1 << bit;
                node = node.children[wanted];
            } else {
                node = node.children[current];
            }
        }
        return value;
    }
}

type xorNode struct {
    children [2]*xorNode
}

func findMaximumXOR(nums []int) int {
    root := &xorNode{}
    insertXOR(root, nums[0])

    answer := 0
    for i := 1; i < len(nums); i++ {
        value := queryXOR(root, nums[i])
        if value > answer {
            answer = value
        }
        insertXOR(root, nums[i])
    }
    return answer
}

func insertXOR(root *xorNode, num int) {
    node := root
    for bit := 30; bit >= 0; bit-- {
        value := (num >> bit) & 1
        if node.children[value] == nil {
            node.children[value] = &xorNode{}
        }
        node = node.children[value]
    }
}

func queryXOR(root *xorNode, num int) int {
    node := root
    value := 0
    for bit := 30; bit >= 0; bit-- {
        current := (num >> bit) & 1
        wanted := current ^ 1
        if node.children[wanted] != nil {
            value |= 1 << bit
            node = node.children[wanted]
        } else {
            node = node.children[current]
        }
    }
    return value
}

复杂度分析

时间复杂度：$O(31n)$，固定整数位宽下即 $O(n)$；每个数字只查询和插入各一次。

空间复杂度：$O(31n)$，最坏情况下每个数字创建一条 31 层路径。

关键点总结

最大异或要从高位贪心，高位的一个 1 无法被所有低位补偿。

Trie 的作用不是排序数字，而是快速判断某个二进制前缀是否存在。

查询过程中始终沿真实存在的前缀前进，所以每一位的局部最优能够组成一个实际数字。

本题输入非负且最高不超过 $2^31 - 1$，处理第 30 位到第 0 位即可。

也可用前缀哈希集合逐位验证候选答案，同为 $O(31n)$；0-1 Trie 更直观地保留了前缀路径。

易错点总结

从低位向高位贪心：低位收益可能被更高位轻易推翻。

插入与查询的位数或顺序不一致：Trie 层级错位，可能走到空节点。

相反位不存在仍强行进入：会发生空指针；此时必须退回同位孩子。

漏掉高位：大数的关键差异被截断，结果偏小。

将位序号直接加入答案：应设置位权 1 << bit，而不是累加 bit。

相似题目

题目	难度	考察点
LCR 067. 数组中两个数的最大异或值	中等	同题换皮，可直接套用同一份二进制 Trie
208. 实现 Trie (前缀树)	中等	字符版前缀树的基本增查，孩子有 26 个分支
211. 添加与搜索单词 - 数据结构设计	中等	带通配符的 Trie 查询，需要在树上做回溯
1310. 子数组异或查询	中等	用异或前缀和快速回答区间异或，不需要贪心
137. 只出现一次的数字 II	中等	同样是拆位思想，但按位统计计数而非建树
477. 汉明距离总和	中等	逐位统计 0/1 个数求所有数对贡献，无需两两枚举