0421. Maximum XOR of Two Numbers in an Array¶
题目信息¶
- 题号:
0421
- 难度:
Medium
- 主题:
非负整数、按位异或、二元选择、最大结果
- 原题:
- 重点:
从数组中选择两个下标
i <= j、计算完整整数的按位异或、只返回最大异或值
题目重述¶
给定非负整数数组 nums,在所有满足 0 <= i <= j < nums.length 的下标对中,计算 nums[i] XOR nums[j],返回能够得到的最大值。
nums.length 位于 [1, 2 * 10^5],每个元素位于 [0, 2^31-1]。允许 i == j,此时异或结果为 0;当数组中有多个下标对取得同一最大值时,仍只返回该最大整数,不需要返回下标或元素。
自建示例¶
最大值来自不同大小的两个数:
输入:nums = [2, 7, 10]
输出:13
解释:7 XOR 10 = 13,大于 2 XOR 7 = 5 和 2 XOR 10 = 8,因此最大异或值为 13。
只有一个元素:
输入:nums = [19]
输出:0
解释:唯一允许的下标对是 i = j = 0,任何整数与自身异或都等于 0。
按最高位贪心保留可行前缀¶
异或结果的高位比低位重要。将所有数插入二进制 trie 后,查询一个数时从最高位到最低位尽量选择与当前位相反的分支:若该分支存在,就能让这一位为 1;否则只能走相同位。因为高位决策优先级更高,这样得到与该数配对的最大异或值。
数组值不超过 2^31-1,从第 30 位向下检查即可;允许同一个下标配对不会影响结果,至少一个数时最大值也会由查询得到。
C++ 实现¶
class Solution {
struct Node {
int child[2] = {-1, -1};
};
std::vector<Node> trie;
void insert(int value) {
int node = 0;
for (int bit = 30; bit >= 0; --bit) {
int current = (value >> bit) & 1;
if (trie[node].child[current] == -1) {
trie[node].child[current]
= static_cast<int>(trie.size());
trie.push_back(Node());
}
node = trie[node].child[current];
}
}
int bestWith(int value) const {
int node = 0;
int result = 0;
for (int bit = 30; bit >= 0; --bit) {
int current = (value >> bit) & 1;
int wanted = current ^ 1;
if (trie[node].child[wanted] != -1) {
result |= 1 << bit;
node = trie[node].child[wanted];
} else {
node = trie[node].child[current];
}
}
return result;
}
public:
int findMaximumXOR(std::vector<int>& nums) {
trie.clear();
trie.push_back(Node());
for (int value : nums) insert(value);
int answer = 0;
for (int value : nums) {
answer = std::max(answer, bestWith(value));
}
return answer;
}
};
代码分析¶
Trie 中的每条路径代表一个完整数的位前缀;查询优先尝试相反位,若存在就不会牺牲已确定的高位最优性。插入和查询各检查 31 位,时间复杂度为 O(31n),额外空间为 O(31n)。