题目描述
给定一个整数数组 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 = [0]
输出：0
示例 3：
输入：nums = [2,4]
输出：6
示例 4：
输入：nums = [8,10,2]
输出：10
示例 5：
输入：nums = [14,70,53,83,49,91,36,80,92,51,66,70]
输出：127
提示：
1 <= nums.length <= 2 * 1040 <= nums[i] <= 231 - 1
进阶：你可以在 O(n) 的时间解决这个问题吗？
注意：本题与主站 421 题相同： https://leetcode.cn/problems/maximum-xor-of-two-numbers-in-an-array/
解法
方法一：哈希表
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19 | class Solution:
def findMaximumXOR(self, nums: List[int]) -> int:
max = 0
mask = 0
for i in range(30, -1, -1):
current = 1 << i
# 期望的二进制前缀
mask = mask ^ current
# 在当前前缀下, 数组内的前缀位数所有情况集合
s = set()
for num in nums:
s.add(num & mask)
# 期望最终异或值的从右数第i位为1, 再根据异或运算的特性推算假设是否成立
flag = max | current
for prefix in s:
if prefix ^ flag in s:
max = flag
break
return max
|
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 | class Solution {
public int findMaximumXOR(int[] numbers) {
int max = 0;
int mask = 0;
for (int i = 30; i >= 0; i--) {
int current = 1 << i;
// 期望的二进制前缀
mask = mask ^ current;
// 在当前前缀下, 数组内的前缀位数所有情况集合
Set<Integer> set = new HashSet<>();
for (int j = 0, k = numbers.length; j < k; j++) {
set.add(mask & numbers[j]);
}
// 期望最终异或值的从右数第i位为1, 再根据异或运算的特性推算假设是否成立
int flag = max | current;
for (Integer prefix : set) {
if (set.contains(prefix ^ flag)) {
max = flag;
break;
}
}
}
return max;
}
}
|
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
45 | class Trie {
public:
vector<Trie*> children;
string v;
Trie()
: children(2) {}
void insert(int x) {
Trie* node = this;
for (int i = 30; ~i; --i) {
int v = (x >> i) & 1;
if (!node->children[v]) node->children[v] = new Trie();
node = node->children[v];
}
}
int search(int x) {
Trie* node = this;
int res = 0;
for (int i = 30; ~i; --i) {
int v = (x >> i) & 1;
if (node->children[v ^ 1]) {
res = res << 1 | 1;
node = node->children[v ^ 1];
} else {
res <<= 1;
node = node->children[v];
}
}
return res;
}
};
class Solution {
public:
int findMaximumXOR(vector<int>& nums) {
Trie* trie = new Trie();
int ans = 0;
for (int v : nums) {
trie->insert(v);
ans = max(ans, trie->search(v));
}
return ans;
}
};
|
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 | type Trie struct {
children [26]*Trie
}
func newTrie() *Trie {
return &Trie{}
}
func (this *Trie) insert(x int) {
node := this
for i := 30; i >= 0; i-- {
v := (x >> i) & 1
if node.children[v] == nil {
node.children[v] = newTrie()
}
node = node.children[v]
}
}
func (this *Trie) search(x int) int {
node := this
res := 0
for i := 30; i >= 0; i-- {
v := (x >> i) & 1
if node.children[v^1] != nil {
res = res<<1 | 1
node = node.children[v^1]
} else {
res <<= 1
node = node.children[v]
}
}
return res
}
func findMaximumXOR(nums []int) int {
trie := newTrie()
ans := 0
for _, v := range nums {
trie.insert(v)
ans = max(ans, trie.search(v))
}
return ans
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23 | class Solution {
func findMaximumXOR(_ numbers: [Int]) -> Int {
var max = 0
var mask = 0
for i in stride(from: 30, through: 0, by: -1) {
let current = 1 << i
mask ^= current
var set = Set<Int>()
for num in numbers {
set.insert(mask & num)
}
let flag = max | current
for prefix in set {
if set.contains(prefix ^ flag) {
max = flag
break
}
}
}
return max
}
}
|
方法二：前缀树
题目是求两个元素的异或最大值，可以从最高位开始考虑。
我们把数组中的每个元素 $x$ 看作一个 $32$ 位的 $01$ 串，按二进制从高位到低位的顺序，插入前缀树（最低位为叶子节点）。
搜索 $x$ 时，尽量走相反的 $01$ 字符指针的策略，因为异或运算的法则是相同得 $0$，不同得 $1$，所以我们尽可能往与 $x$ 当前位相反的字符方向走，才能得到能和 $x$ 产生最大值的结果。