数组中两个数的最大异或值
难度:
标签:
题目描述
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 * 1050 <= nums[i] <= 231 - 1
代码结果
运行时间: 91 ms, 内存: 41.9 MB
/*
* 题目思路：
* 虽然字典树（Trie）通常不能直接用流式处理，但我们可以使用函数式编程思想进行分步操作。
* 这里我们先构建字典树，然后使用流来处理数组。
*/
import java.util.*;
import java.util.stream.*;
class Solution {
// 字典树节点类
class TrieNode {
TrieNode[] children = new TrieNode[2];
}
// 字典树的根节点
private TrieNode root = new TrieNode();
// 在字典树中插入一个数字
private void insert(int num) {
TrieNode node = root;
for (int i = 31; i >= 0; i--) {
int bit = (num >> i) & 1;
if (node.children[bit] == null) {
node.children[bit] = new TrieNode();
}
node = node.children[bit];
}
}
// 在字典树中查找最大异或值
private int findMaximumXOR(int num) {
TrieNode node = root;
int maxXOR = 0;
for (int i = 31; i >= 0; i--) {
int bit = (num >> i) & 1;
int oppositeBit = bit ^ 1;
if (node.children[oppositeBit] != null) {
maxXOR = (maxXOR << 1) | 1;
node = node.children[oppositeBit];
} else {
maxXOR = (maxXOR << 1);
node = node.children[bit];
}
}
return maxXOR;
}
public int findMaximumXOR(int[] nums) {
Arrays.stream(nums).forEach(this::insert);
return Arrays.stream(nums)
.map(this::findMaximumXOR)
.max()
.orElse(0);
}
}解释
方法:
该题解采用了二进制前缀树（Trie）的思想。从最高位开始，逐位尝试将最大异或值 ans 的当前位设为 1。对于每一位，我们维护一个集合 seen，存储之前遍历过的数在当前位及更高位上的部分。如果能找到一个数，使得它与 newAns 的异或结果在 seen 中，说明 newAns 是可以达到的，我们将 ans 更新为 newAns。
时间复杂度:
O(nL)
空间复杂度:
O(n)
代码细节讲解
🦆
在构建二进制前缀树的过程中，你是如何确定从最高位开始而不是从最低位开始？
▷🦆
为什么在遍历每一位时需要使用掩码 `mask`，具体的目的和作用是什么？
▷🦆
在题解中，`seen` 集合存储的是 `num & mask` 的结果，这样操作的目的是什么，它如何帮助找到最大的 XOR 值？
▷