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

约 9 分钟
文章信息 5 个分类 5 个标签
分类
LeetCode 中等 119 经典题变种挑战 剑指 Offer 剑指 Offer（专项突击版）
标签
数组 哈希表 LCR 位运算 字典树
目录

题目描述

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

题意分析

给一个非负整数数组，从中任选两个数求异或，问这个异或值最大能是多少。

异或的性质决定了这题的形状：结果的每一位互不影响，第 $i$ 位为 1 当且仅当两个数的第 $i$ 位不同。而比较大小时高位的权重压倒一切——只要能让第 30 位取到 1，低 30 位无论怎样都比不上。这直接指向按位从高到低逐位贪心。

约束里元素个数可达 $2 \times 10^5$，取值上限 $2^{31} - 1$。$n^2$ 的枚举是 $4 \times 10^{10}$ 次运算，完全不可行；而位数只有 31，说明复杂度应当是 $O(n \cdot 31)$ 这种「元素数乘位数」的形态。

注意题目要求的是「任选两个数」，两个数可以取值相同（来自不同下标），此时异或为 0；数组长度至少为 1，只有一个元素时无法组成数对，答案是 0。

边界上要注意：数组可能全部相同，答案为 0；可能含 0；取值上限是 $2^{31}-1$，用 31 位（下标 30 到 0）扫描即可覆盖，不要漏掉最高位也不要多扫到符号位。

解法：哈希表统计状态

核心思路

暴力做法是二重循环枚举所有数对求异或取最大，$O(n^2)$。在 $n = 2 \times 10^5$ 时是 $4 \times 10^{10}$ 次运算，必然超时。

瓶颈在于它把「最大异或值」当成一个不可分解的整体去搜索，而实际上答案是逐位构成的：一旦确定了答案的高位形态，低位的搜索空间会被大幅裁剪。

观察的切入点是「从高位往低位贪心地确定答案」。假设已经确定答案的高若干位是某个值 ans，现在考察下一位能否取 1，也就是问：能否找到两个数，它们的高位部分异或恰好等于 flag = ans | (1 << i)？如果能，这一位就该取 1（高位取 1 永远优于取 0）；如果不能，这一位只能是 0，ans 保持不变。

「高位部分」用掩码 mask 来截取：mask 是从第 30 位到第 i 位全为 1 的前缀掩码，v & mask 就是 v 的高位前缀。于是问题变成：在所有前缀构成的集合里，是否存在两个前缀 a、b 满足 a ^ b == flag。

这个判定可以用异或的自反性化简：a ^ b == flag 等价于 b == a ^ flag。所以只需把当前所有前缀塞进一个哈希集合，再遍历集合中的每个 a，查 a ^ flag 是否也在集合中——存在即说明这一位可以取 1。一次判定是 $O(n)$，整体 $O(31n)$。

维持的不变量是：每一轮结束时，ans 恰好是「所有数对异或值的高位前缀」所能达到的最大值。因为高位优先且每一位都在「能取 1 就取 1」的前提下确定，逐位贪心得到的结果就是全局最大值；而 flag 之所以要带上已确定的高位 ans 而不只是当前位，正是为了保证找到的那对数在高位上也必须维持已达成的最优形态，不能为了新的一位牺牲旧的高位。

解题步骤

  • 初始化 ans = 0、mask = 0，从第 30 位向第 0 位循环。取 30 是因为元素上限 $2^{31} - 1$ 的最高有效位就是第 30 位，再往上全是 0，扫描它们纯属浪费；也不能扫到第 31 位的符号位。
  • 每轮先把当前位并入掩码：mask |= 1 << i。掩码累积而不是只保留当前位，是因为判定要基于「从最高位到当前位的整个前缀」，只看单独一位无法维持已确定的高位形态。
  • 用掩码截取所有元素的高位前缀，放进哈希集合。集合天然去重，重复前缀只判定一次，这是把 $O(n^2)$ 压到 $O(n)$ 的关键。
  • 令候选答案 flag = ans | (1 << i)，也就是「保持已确定的高位不变，再让当前位取 1」。flag 必须带上 ans，只用当前位会导致高位的最优性在后续轮次被破坏。
  • 遍历集合中的每个前缀 a，检查 a ^ flag 是否也在集合中。命中即说明存在这样一对数，把 ans 更新为 flag 并立即跳出——同一轮里找到一个见证就够了。
  • 若整轮都没命中，ans 保持不变，这一位只能是 0。循环结束后返回 ans。

以 nums = [3, 10, 5, 25, 2, 8] 走一遍：最大元素 25 的二进制是 11001，所以第 5 位以上的轮次里所有前缀都是 0，flag 永远无法命中，ans 保持 0。到第 4 位（值 16）时 mask = 16，前缀集合是 {0, 16}（只有 25 的第 4 位是 1），flag = 16，取 a = 0 查 0 ^ 16 = 16 在集合中，命中，ans = 16。第 3 位时 mask = 24，前缀集合是 {0, 8, 24}，flag = 16 | 8 = 24，遍历发现 0 ^ 24 = 24 在集合中，命中，ans = 24。第 2 位时 mask = 28，前缀集合是 {0, 8, 4, 24}，flag = 24 | 4 = 28，检查 0^28=28 不在、8^28=20 不在、4^28=24 在集合中，命中，ans = 28。第 1 位时 mask = 30，前缀集合是 {2, 10, 4, 24, 2, 8} 去重后为 {2, 10, 4, 24, 8}，flag = 28 | 2 = 30，逐个检查 2^30=28、10^30=20、4^30=26、24^30=6、8^30=22 均不在集合中，这一位取 0，ans 仍为 28。第 0 位时 mask = 31，flag = 29，同样无人命中，ans = 28。返回 28，正是 5 ^ 25 的结果。

代码实现

class Solution {

    public int findMaximumXOR(int[] numbers) {
        int max = 0;
        int mask = 0;
        for (int i = 30; i >= 0; i--) {
            int current = 1 << i;
            mask = mask ^ current;
            Set<Integer> set = new HashSet<>();
            for (int j = 0, k = numbers.length; j < k; j++) {
                set.add(mask & numbers[j]);
            }
            int flag = max | current;
            for (Integer prefix : set) {
                if (set.contains(prefix ^ flag)) {
                    max = flag;
                    break;
                }
            }
        }
        return max;
    }
}

func findMaximumXOR(nums []int) int {
    ans, mask := 0, 0
    for i := 30; i >= 0; i-- {
        cur := 1 << i
        mask |= cur
        seen := make(map[int]bool, len(nums))
        for _, v := range nums {
            seen[v&mask] = true
        }
        flag := ans | cur
        for p := range seen {
            if seen[p^flag] {
                ans = flag
                break
            }
        }
    }
    return ans
}

复杂度分析

  • 时间复杂度：$O(31n)$，也就是 $O(n \log C)$。外层固定 31 轮，每轮构建前缀集合与遍历判定各需 $O(n)$ 次常数级哈希操作。
  • 空间复杂度：$O(n)$，每轮重建的哈希集合至多存下 $n$ 个不同的前缀，轮次之间不累积。

关键点总结

  • 求「最大异或」「最大与」这类位运算极值，通用套路是从高位到低位贪心：高位的权重大于所有低位之和，能取 1 就必须取 1，绝不为低位让步。
  • a ^ b == target 与 b == a ^ target 等价，这条自反性把「枚举数对」降成「枚举单个数 + 一次查表」，是把 $O(n^2)$ 压到 $O(n)$ 的核心变换。
  • 候选值必须带上已确定的高位（flag = ans | cur），而不是只测当前位。贪心的正确性依赖「每一步都在已有最优前提下扩展」，丢掉前缀就退化成了各位独立判断，结果必错。
  • 掩码要逐轮累积成前缀掩码。截取的粒度决定了判定的语义，只留单独一位等于放弃了高位约束。
  • 位数上界要根据数值范围定，而不是随手写 32。多扫符号位会引入负数干扰，少扫最高有效位会直接丢掉答案的最高位。
  • 面试视角：这题有哈希贪心与 0-1 字典树两种主流写法，复杂度同为 $O(31n)$。哈希写法代码短、白板上不易出错；字典树写法更直观（每一位都尽量走相反的分支）且能自然扩展到「带下标/权值限制」的变种。开场时点明两条路线并说明选择理由，比闷头写一种更能拿分。
  • 面试视角：常见追问是「如果限制两数下标之差不超过 $k$」或「如果给定上界求不超过上界的最大异或」。前者答滑动窗口配合可删除的字典树，后者答在字典树上带着上界一起走，思路都建立在同一套按位贪心之上。

易错点总结

  • 错误写法：flag 只取当前位，写成 flag = 1 << i。用例 nums = [8, 10, 2] → 第 3 位判定成功后，第 1 位又用不带高位的 flag 单独判定并覆盖 ans，最终结果丢掉了已确定的高位，答案偏小。
  • 错误写法：掩码不累积，每轮只用当前位 mask = 1 << i。用例 nums = [3, 10, 5, 25, 2, 8] → 前缀退化成单个比特，各位独立判断都能取到 1，返回 31，而真实的最大异或是 28，因为没有任何一对数能同时满足所有位。
  • 错误写法：位循环从 31 开始。用例 nums = [2147483647, 0] → 第 31 位是 int 的符号位，1 << 31 为负数，掩码与候选值都变成负数，判定逻辑与结果全部错乱。
  • 错误写法：位循环只到第 15 位或用 while (max > 0) 之类的提前退出。用例 nums = [1073741824, 0] → 最高位在第 30 位，早停会直接丢掉它，返回 0，正确答案是 1073741824。
  • 错误写法：判定时写成 set.contains(flag ^ prefix) 却把 prefix 取自原始数组而非掩码截断后的前缀。用例 nums = [3, 10, 5, 25, 2, 8] → 低位噪声让 prefix ^ flag 几乎永远查不中，ans 长期停在 0，结果偏小。
  • 错误写法：用列表而不是集合存前缀，判定时线性查找。用例 n = 200000 → 每轮判定退化成 $O(n^2)$，总量 $10^{12}$，必然超时；哈希查表的 $O(1)$ 正是这个解法成立的前提。
  • 错误写法：命中后不 break，继续遍历并可能重复赋值。用例 任意数组 → 结果虽仍正确，但每轮固定跑满 $O(n)$ 次哈希查询，在极端数据下常数明显变差；找到一个见证就足以确定这一位。
  • 错误写法：认为答案一定由数组中最大值参与产生，只拿最大值去和其它数异或。用例 nums = [8, 10, 2] → 最大值 10 与其它数异或得 10^8=2、10^2=8，返回 8，而 8 ^ 2 = 10 才是正确答案。
  • 错误写法：把「任选两个数」理解成必须下标不同且值也不同，提前对数组去重后再判断长度。用例 nums = [5, 5] → 去重后只剩一个元素，直接返回 0 虽然结果凑巧正确，但换成 nums = [5, 5, 3] 时若因去重而漏算重复元素参与的数对，逻辑已不可靠；正确做法是不做任何去重，让贪心自然处理。

相似题目

题目 难度 考察点
421. 数组中两个数的最大异或值 中等 与本题同题，可用来对照哈希贪心与 0-1 字典树两种实现
208. 实现 Trie (前缀树) 中等 字典树解法的结构基础，只是分支从 26 路收缩为 2 路
137. 只出现一次的数字 II 中等 同样逐位独立处理，但用的是计数取模而非高位贪心
268. 丢失的数字 简单 利用异或的自反性抵消成对元素，是本题化简判定式的同一条性质
1268. 搜索推荐系统 中等 同为前缀结构上的查询，但比较键是字符而非比特且要返回多个候选
745. 前缀和后缀搜索 困难 也靠预处理把配对查询压成查表，键的构造方式更复杂