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

约 6 分钟
文章信息 7 个分类 4 个标签
分类
LeetCode CodeTop 中等 未解决 5-10 字节 微软
标签
数组 哈希表 位运算 字典树

题目描述

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

image-20260928235544712

题意分析

从数组中选择两个数，使异或结果最大；题目允许选择同一个位置，其异或结果为 0。异或的每一位在两个数对应位不同时为 1，相同时为 0。

数值范围是 0 到 2^31 - 1，只需要处理第 30 位到第 0 位。可以逐个处理数组元素，为当前数寻找此前元素中最有利的配对，再取所有查询结果的最大值。

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

核心思路

[!blue]

把已经处理过的数存入二进制字典树。每个数从第 30 位到第 0 位走一条完整路径，节点的两个孩子分别代表下一位取 0 或 1；多个数具有相同高位前缀时，共用同一段路径。

查询当前数时也从高位开始。若当前位是 current，优先选择 wanted = current ^ 1 对应的孩子，让异或结果的这一位为 1。在更高位已经确定的前提下，第 bit 位的贡献是 $2^{bit}$，而所有更低位加起来最多只有 $2^{bit}-1$，因此只要能让当前位为 1，就不应为了低位而放弃它。

每次选择都沿当前节点的某个现存孩子继续，相当于只保留与已选前缀一致的候选数，保证最后得到的路径属于一个真实存入的数。不能在不同候选之间独立挑选各位，否则拼出的配对可能不存在。

相反位分支存在时，把查询结果 value 的对应位设为 1；不存在时只能走同位分支，该位贡献 0。字典树中至少有一个完整的数，因此走到的节点总有下一层可选分支，直到全部 31 位处理完。

先插入第一个数，之后每个数都先查询、再插入。任意两个不同位置的配对，都会在处理较后位置时进入候选范围；同一位置与自身异或只会得到 0，由初始答案覆盖即可。这样也自然处理了只有一个元素的情况。

解题步骤

  1. 创建空字典树，从高位到低位插入 nums[0]，不存在的分支就新建节点。
  2. 将全局答案初始化为 0，从第二个数开始处理。
  3. 查询时从根出发，在每一位优先走与当前数相反的分支，并设置异或结果对应位；没有相反分支时走同位分支。
  4. 查询结束后，用这次得到的最大异或值更新全局答案，再把当前数插入字典树。
  5. 所有数处理完后返回答案。

代码实现

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)$，每个数的插入和查询都只经过 31 层；位宽固定时即为 $O(n)$。
  • 空间复杂度：$O(31n)$，每次插入最多新增 31 个节点，实际节点数会因共享前缀而减少。

关键点总结

[!green]

  • 贪心依据是高位的权重大于所有低位之和，而不是只尽量增加异或结果中 1 的个数。
  • 字典树路径保留候选数之间的位关联，保证每次查询对应一个真实配对。
  • 查询得到的是最大异或值，不需要额外还原配对元素本身。
  • 先查询再插入逐步加入候选；重复数可以共用同一条路径。

易错点总结

[!yellow]

  • 必须从高位向低位贪心。先优化低位可能阻碍更高位取得 1，从而得到更小结果。
  • 插入与查询要使用相同的位宽和方向；本题非负 31 位整数从第 30 位开始即可。
  • 相反分支不存在时不能结束查询，仍需沿同位分支继续优化后面的位。
  • 查询前字典树必须非空；代码先插入第一个数，单元素输入直接返回初始答案 0。

相似题目

题目 难度 关联与区别
1707. 与数组中元素的最大异或值 困难 同样用二进制Trie贪心选择相反位，原题还限制参与查询的数值上界。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2025/82578647
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！