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

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

示例 1：

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

示例 2：

1
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

按位哈希：对于每一位，用哈希表记录之前出现的数，用哈希表判断newRes是否可能成立

如果 a⊕b=newAns，那么两边同时异或 b，由于 b⊕b=0，所以得到 a=newAns⊕b（相当于把两数之和代码中的减法改成异或）

这样就可以一边枚举 b，一边在哈希表中查找 newAns⊕b 了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int findMaximumXOR(int[] nums) {
        int n = nums.length, max = Arrays.stream(nums).max().getAsInt();
        int highBit = 31 - Integer.numberOfLeadingZeros(max);
        int res = 0, mask = 0;
        Set<Integer> vis = new HashSet<>();
        for (int i = highBit; i >= 0; i--) {  // 从最高位开始考虑
            vis.clear();
            mask |= 1 << i;  // 高位都是1的mask
            int newRes = res | (1 << i);
            for (int x : nums) {  // 考虑当前位能否取到1（前缀+哈希表的思路）
                x &= mask;  // 低于 i 的比特位置为 0
                if  (vis.contains(newRes ^ x)) {
                    res = newRes;  // newRes成立，这个比特位可以是 1
                    break;
                }
                vis.add(x);
            }
        }
        return res;
    }
}

字典树，search的时候往取反的值找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
class Trie {
    class TrieNode {
        boolean end;
        TrieNode[] children = new TrieNode[2];
    }
    TrieNode root = new TrieNode();
    void insert(int word) {
        TrieNode cur = root;
        for (int i = 30; i >= 0; i--) {
            int index = word >> i & 1;
            if (cur.children[index] == null) {
                cur.children[index] = new TrieNode();
            }
            cur = cur.children[index];
        }
        cur.end = true;
    }
    int search(int word) {
        TrieNode cur = root;
        int res = 0;
        for (int i = 30; i >= 0; i--) {  // 对于每一位，它检查是否存在与当前位不同的子节点（即 index ^ 1）
            int index = word >> i & 1;
            if (cur.children[index ^ 1] == null) {  // 如果不存在，它继续在当前子节点上处理下一位
                cur = cur.children[index];  // 因为先insert当前word，所以children[index]肯定存在
            }
            else {  // 如果存在，说明可以通过选择相反的位来最大化异或结果，因此它将结果 res 更新为当前位的最大值，并将当前节点移动到相反的子节点
                res |= 1 << i;
                cur = cur.children[index ^ 1];
            }
        }
        return res;
    }
}
class Solution {
    public int findMaximumXOR(int[] nums) {
        int n = nums.length, res = 0;
        Trie tree = new Trie();
        for (int x : nums) {
            tree.insert(x);
            res = Math.max(res, tree.search(x));
        }
        return res;
    }
}