0421.md

title	description	keywords
421. 数组中两个数的最大异或值	LeetCode 421. 数组中两个数的最大异或值题解，Maximum XOR of Two Numbers in an Array，包含解题思路、复杂度分析以及完整的 JavaScript 代码实现。	LeetCode 421. 数组中两个数的最大异或值 数组中两个数的最大异或值 Maximum XOR of Two Numbers in an Array 解题思路 位运算 字典树 数组 哈希表

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

🟠 Medium  🔖  位运算 字典树 数组 哈希表  🔗 力扣 LeetCode

题目

Given an integer array nums, return the maximum result of nums[i] XOR nums[j], where 0 <= i <= j < n.

Example 1:

Input: nums = [3,10,5,25,2,8]

Output: 28

Explanation: The maximum result is 5 XOR 25 = 28.

Example 2:

Input: nums = [14,70,53,83,49,91,36,80,92,51,66,70]

Output: 127

Constraints:

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

题目大意

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

示例 1：

输入： nums = [3,10,5,25,2,8]

输出： 28

解释： 最大运算结果是 5 XOR 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. 观察异或的性质 异或（XOR）的重要特性：

   • a ^ a = 0
   • a ^ 0 = a
   • 异或运算的结果越大，意味着两个数的二进制表示越不同。

   题目要求在 nums 数组中找到两个数 a 和 b，使 a ^ b 的值最大，即：max(a ^ b)

2. 逐位构造最大异或值

   • 从最高位到最低位 逐步确定 max 的每一位是否可以为 1。
   • 维护一个掩码 mask，用于保留当前考虑的高位部分。
   • 用哈希集合 set 记录所有数的前缀（保留 mask 位）。

3. 贪心推导最大值 假设 max 目前的值是 X，希望新的一位也能是 1：

   • 计算 temp = max | (1 << i)，即尝试将 i 位置为 1。
   • 遍历哈希集合 set，查找是否存在 prefix1 和 prefix2 使： prefix1 ^ prefix2 = temp
   • 如果找到了，说明 max 可以取 temp，否则 max 保持不变。

4. 初始化

   • max = 0：存储最大异或值。
   • mask = 0：用于保留高 i 位。
   • i 从 31 到 0 遍历（因为 nums[i] 在 JavaScript 中是 32 位整数）。

5. 遍历构造最大值

   • 更新 mask，保留当前高 i 位。
   • 遍历 nums，用 mask 提取所有前缀存入 set。
   • 尝试更新 max：
     • 假设新 max 值 temp = max | (1 << i)。
     • 检查 set 是否存在 prefix1 和 prefix2 使 prefix1 ^ prefix2 == temp。
     • 如果存在，则更新 max = temp。

6. 返回最大异或值 最终 max 存储了最大的 a ^ b 结果。

复杂度分析

• 时间复杂度：O(32 * n) = O(n)，外层循环运行 32 次，内层循环遍历 nums 计算哈希集合 set，时间复杂度 O(n)。
• 空间复杂度：O(n)，哈希集合 set 最多存储 n 个不同的前缀值。

代码

/**
 * @param {number[]} nums
 * @return {number}
 */
var findMaximumXOR = function (nums) {
	let max = 0;
	let mask = 0;

	for (let i = 31; i >= 0; i--) {
		mask |= 1 << i; // 保留当前最高的 i 位
		let set = new Set();

		for (let num of nums) {
			set.add(num & mask); // 仅保留前 i 位
		}

		let temp = max | (1 << i); // 期望 i 位置为 1
		for (let prefix of set) {
			if (set.has(temp ^ prefix)) {
				// 是否存在 prefix1 和 prefix2 使 prefix1 ^ prefix2 = temp
				max = temp;
				break;
			}
		}
	}

	return max;
};

相关题目

题号	标题	题解	标签	难度	力扣
1707	与数组中元素的最大异或值		位运算 字典树 数组	🔴	🀄️ 🔗
2317	操作后的最大异或和		位运算 数组 数学	🟠	🀄️ 🔗
2416	字符串的前缀分数和	[✓]	字典树 数组 字符串 1+	🔴	🀄️ 🔗
2429	最小异或	[✓]	贪心 位运算	🟠	🀄️ 🔗
2932	找出强数对的最大异或值 I		位运算 字典树 数组 2+	🟢	🀄️ 🔗
2935	找出强数对的最大异或值 II		位运算 字典树 数组 2+	🔴	🀄️ 🔗