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

🟠   🔖  位运算 字典树 数组 哈希表  🔗 力扣 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+	🔴	🀄️ 🔗