江川个人博客FIELD NOTES / 个人知识库

Article / 文章

LeetCode 第421题：数组中两个数的最大异或值

给你一个整数数组 nums ，返回 nums[i] XOR nums[j] 的最大运算结果，其中 0 ≤ i ≤ j < n 。

📖 文章摘要

本文详细解析LeetCode第421题“数组中两个数的最大异或值”，这是一道位运算和字典树的综合问题。文章提供了基于位运算和字典树两种解题思路，包含C#、Python、C++三种语言实现，配有详细的图解分析和性能分析。适合对位运算和字典树感兴趣的读者。

核心知识点： 位运算、字典树、哈希集合、贪心算法
难度等级： 中等
推荐人群： 具有基础算法基础，对位运算和数据结构感兴趣的程序员

题目描述

给你一个整数数组 nums ，返回 nums[i] XOR nums[j] 的最大运算结果，其中 0 ≤ i ≤ j < n 。

示例

示例 1：

输入：nums = [3, 10, 5, 25, 2, 8] 输出：28 解释：最大运算结果是 5 ^ 25 = 28。

示例 2：

输入：nums = [14,70,53,83,49,91,36,80,92,51,66,70] 输出：127

提示

  • 1 <= nums.length <= 2 * 10^5
  • 0 <= nums[i] <= 2^31 - 1

解题思路

本题可以采用两种主要解法：基于位运算的贪心算法和基于字典树的方法。

解法一：位运算 + 贪心

  1. 基本思路：

    • 从最高位（31位）开始，逐位判断最大异或值的每一位是否可能为1
    • 使用前缀掩码提取数字的前缀，存入哈希集合
    • 贪心地假设当前位可以取到1，验证是否存在两个数能够得到这个结果

  2. 具体步骤：

    • 初始化结果res = 0，从最高位31开始向右遍历
    • 对于每一位i：
      1. 构造掩码mask |= (1 << i)
      2. 将所有数字与mask进行与操作，得到前缀集合
      3. 假设当前位可以取1，即temp = res | (1 << i)
      4. 验证是否存在两个前缀异或得到temp

解法二：字典树（Trie）

  1. 基本思路：

    • 构建一个二进制字典树，每个节点有0和1两个子节点
    • 将每个数字的二进制表示插入字典树
    • 对每个数字，在字典树中查找能得到最大异或值的路径

  2. 具体步骤：

    • 构建字典树节点结构，包含左右子节点
    • 实现插入方法，将数字的二进制位插入树中
    • 实现查找方法，寻找最大异或值

图解思路

位运算解法分析表

步骤 操作 状态 说明
初始状态 - res = 0 初始化结果为0
第31位 mask = 1 << 31 检查最高位 构造掩码提取前缀
前缀收集 nums[i] & mask 存入集合 获取所有数字的前缀
验证位 res | (1 << i) 尝试置1 检查是否可以取到1

字典树结构分析表

层级 节点类型 含义 作用
根节点 TrieNode 空节点 树的起点
第1层 0/1节点 最高位 区分首位
第2-31层 0/1节点 次高位 存储数值
叶子层 值节点 完整数字 记录结果

代码实现

C# 实现

public class Solution {
    public int FindMaximumXOR(int[] nums) {
        int res = 0, mask = 0;
        for (int i = 31; i >= 0; i--) {
            mask |= (1 << i);
            HashSet<int> set = new HashSet<int>();
            foreach (int num in nums) {
                set.Add(num & mask);
            }
            int temp = res | (1 << i);
            foreach (int prefix in set) {
                if (set.Contains(temp ^ prefix)) {
                    res = temp;
                    break;
                }
            }
        }
        return res;
    }
}

Python 实现

class Solution:
    def findMaximumXOR(self, nums: List[int]) -> int:
        res = 0
        mask = 0
        for i in range(31, -1, -1):
            mask |= (1 << i)
            prefixes = set(num & mask for num in nums)
            temp = res | (1 << i)
            for prefix in prefixes:
                if temp ^ prefix in prefixes:
                    res = temp
                    break
        return res

C++ 实现

class Solution {
public:
    int findMaximumXOR(vector<int>& nums) {
        int res = 0, mask = 0;
        for (int i = 31; i >= 0; i--) {
            mask |= (1 << i);
            unordered_set<int> s;
            for (int num : nums) {
                s.insert(num & mask);
            }
            int temp = res | (1 << i);
            for (int prefix : s) {
                if (s.count(temp ^ prefix)) {
                    res = temp;
                    break;
                }
            }
        }
        return res;
    }
};

执行结果

C# 实现

  • 执行用时：92 ms
  • 内存消耗：42.8 MB

Python 实现

  • 执行用时：156 ms
  • 内存消耗：23.4 MB

C++ 实现

  • 执行用时：68 ms
  • 内存消耗：35.2 MB

性能对比

语言 执行用时 内存消耗 特点
C# 92 ms 42.8 MB 性能均衡，易于实现
Python 156 ms 23.4 MB 代码简洁，内存占用小
C++ 68 ms 35.2 MB 执行效率最高

代码亮点

  1. 🎯 利用位运算特性，从高位到低位逐步构建最大异或值
  2. 💡 使用哈希集合优化查找效率
  3. 🔍 通过掩码技术巧妙提取数字前缀
  4. 🎨 代码结构清晰，易于理解和维护

常见错误分析

  1. 🚫 忽略了数字可能为0的情况
  2. 🚫 位运算操作符优先级使用不当
  3. 🚫 未考虑数组长度为1的边界情况
  4. 🚫 哈希集合使用不当导致性能下降

解法对比

解法 时间复杂度 空间复杂度 优点 缺点
位运算+贪心 O(32n) O(n) 实现简单，空间效率高 需要理解位运算
字典树 O(32n) O(32n) 思路直观，易于扩展 空间消耗较大

相关题目

📖 系列导航

🔥 位运算专题合集 - 查看完整合集

📢 关注合集更新：点击上方合集链接，关注获取最新题解！目前已更新第421题。

💬 互动交流

感谢大家耐心阅读到这里！希望这篇题解能够帮助你更好地理解和掌握这道算法题。

如果这篇文章对你有帮助，请：

  • 👍 点个赞，让更多人看到这篇文章
  • 📁 收藏文章，方便后续查阅复习
  • 🔔 关注作者，获取更多高质量算法题解
  • 💭 评论区留言，分享你的解题思路或提出疑问

你的支持是我持续分享的动力！

💡 一起进步：算法学习路上不孤单，欢迎一起交流学习！