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

题目

给你一个整数数组 nums, 返回 nums[i] ^ nums[j] 的最大运算结果, 其中 0 <= i <= j < n.

提示:

• 1 <= nums.length <= 2 * 10⁵
• 0 <= nums[i] <= 2³¹ - 1

示例

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

输出: 28

解释: 最大运算结果是 5 ^ 25 = 28.

题解

解决这个问题, 我们首先需要利用异或运算的一个性质:

如果 a ^ b = c 成立, 那么 a ^ c = b 与 b ^ c = a 均成立.

所以你可以理解为: 给定一个数组 nums, 再给定 一个数值 x. 请判断 nums 数组中是否存在两个数, 且这两个数的异或结果值为 x. 暴力法:

for (let i = 1; i < nums.length; ++i) {
  for (let j = 0; j < i; ++j) {
    if (nums[i] ^ (nums[j] === x)) return true
  }
}

如何不使用暴力法解决该问题呢? 假设数组中存在 a 和 b, 满足 a ^ b === x, 则 a ^ x === b 与 b ^ x === a 也必然满足. 反过来讲, 你可以遍历数组 nums, 将当前遍历的数记为 a, 计算 a ^ x, 若数组中存在一个数(记为 b), 满足 b == a ^ x, 则说明数组中存在两个数 a 和 b, 满足 a ^ b === x.

理解了这一点的话, 就可利用 HashSet, 将 nums 数组中所有数值都存入 HashSet, 再如下列代码一样操作:

for (let num of hashSet) {
  if (hashSet.has(num ^ x)) return true
}

JavaScript

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

  for (let i = 30; i >= 0; i--) {
    // 先计算掩码
    mask |= 1 << i

    const set = new Set()
    for (const num of nums) {
      // 通过 num & mask 即可把 nums 中的所有数字以二进制存储进 set 中
      set.add(num & mask)
    }

    const temp = res | (1 << i)
    for (const prefix of set) {
      if (set.has(prefix ^ temp)) {
        res = temp
        break
      }
    }
  }

  return res
}

Rust

use std::collections::HashSet;

pub fn find_maximum_xor(nums: Vec<i32>) -> i32 {
    let mut res = 0;
    let mut mask = 0;

    for i in (0..31).rev() {
        mask |= 1 << i;

        let mut set = HashSet::new();
        for num in &nums {
            set.insert(num & mask);
        }

        let temp = res | (1 << i);
        for prefix in &set {
            if set.contains(&(prefix ^ temp)) {
                res = temp;
                break;
            }
        }
    }

    res
}