问题描述
给定一个非负整数的数组，要求找出数组中两个元素的异或值的最大值。题目链接：点我
样例输入输出
输入：nums = [3,10,5,25,2,8]
输出：28
解释：最大值是 5 XOR 25 = 28
输入：nums = [14,70,53,83,49,91,36,80,92,51,66,70]
输出：127
问题解法
此题最简单的做法就是两层循环分别对两个数字进行异或求解，但是这样时间复杂度是 O(n ^ 2)，会超时。优化的做法是将数组元素的二进制数构造字典树，然后依次取数组中元素，判断每个二进制位，从字典数中取出与其数字（0 对应 1, 1 对应 0）相反的分支，如果不存在此分支则走另外的分支（不存在 0 的分支则走 1 的分支，不存在 1 的分支则走 0 的分支）。需要注意的是构造字典树需要从元素高位构造，从高位进行匹配，因为异或为 1 时，高位的 1 比低位的 1 代表的数值会更大。代码如下
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 Solution {
private static final int TOTAL_DIGITS = 30;
private class Node {
Node[] children = new Node[2];
}
public int findMaximumXOR(int[] nums) {
Node root = buildTree(nums);
int result = 0;
for (int num : nums) {
Node current = root;
int tempResult = 0;
for (int i = TOTAL_DIGITS; i >= 0; i--) {
int bit = (num >> i) & 1;
int index = (~bit) & 1;
if (current.children[index] != null) {
current = current.children[index];
tempResult = (1 << i) | tempResult;
} else {
current = current.children[bit];
}
}
result = Math.max(result, tempResult);
}
return result;
}
private Node buildTree(int[] nums) {
Node root = new Node();
for (int num : nums) {
Node current = root;
for (int i = TOTAL_DIGITS; i >= 0; i--) {
int bit = (num >> i) & 1;
if (current.children[bit] == null) {
current.children[bit] = new Node();
}
current = current.children[bit];
}
}
return root;
}
}
|