0421. 数组中两个数的最大异或值【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 贪心 + 哈希表

1. 📝 题目描述

• leetcode

给你一个整数数组 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

2. 🎯 s.1 - 贪心 + 哈希表

c

#define HASH_SIZE 100003
typedef struct Node { int val; struct Node* next; } Node;

void hashInsert(Node** table, int val) {
    int idx = ((unsigned)val) % HASH_SIZE;
    Node* n = (Node*)malloc(sizeof(Node));
    n->val = val; n->next = table[idx]; table[idx] = n;
}

bool hashContains(Node** table, int val) {
    int idx = ((unsigned)val) % HASH_SIZE;
    for (Node* n = table[idx]; n; n = n->next) if (n->val == val) return true;
    return false;
}

void hashFree(Node** table) {
    for (int i = 0; i < HASH_SIZE; i++) { Node* n = table[i]; while (n) { Node* t = n; n = n->next; free(t); } table[i] = NULL; }
}

int findMaximumXOR(int* nums, int numsSize) {
    int max = 0, mask = 0;
    Node** table = (Node**)calloc(HASH_SIZE, sizeof(Node*));
    for (int i = 31; i >= 0; i--) {
        mask |= (1 << i);
        hashFree(table);
        for (int j = 0; j < numsSize; j++) hashInsert(table, nums[j] & mask);
        int candidate = max | (1 << i);
        for (int j = 0; j < numsSize; j++) {
            if (hashContains(table, (nums[j] & mask) ^ candidate)) { max = candidate; break; }
        }
    }
    free(table);
    return max;
}

js

/**
 * @param {number[]} nums
 * @return {number}
 */
var findMaximumXOR = function (nums) {
  let max = 0,
    mask = 0
  for (let i = 31; i >= 0; i--) {
    mask |= 1 << i
    const set = new Set()
    for (const num of nums) set.add(num & mask)
    const candidate = max | (1 << i)
    for (const prefix of set) {
      if (set.has(prefix ^ candidate)) {
        max = candidate
        break
      }
    }
  }
  return max
}

py

class Solution:
    def findMaximumXOR(self, nums: List[int]) -> int:
        max_xor, mask = 0, 0
        for i in range(31, -1, -1):
            mask |= (1 << i)
            prefixes = {num & mask for num in nums}
            candidate = max_xor | (1 << i)
            if any(prefix ^ candidate in prefixes for prefix in prefixes):
                max_xor = candidate
        return max_xor

• 时间复杂度：$O(32n)$，即 $O(n)$
• 空间复杂度：$O(n)$

算法思路：

• 从最高位到最低位贪心地确定每一位是否可以为 1
• 利用 $a\oplus b=c\iff a\oplus c=b$ 的性质，用哈希表判断候选值是否可达