描述
Given a non-empty array of numbers, a0, a1, a2, … , an-1, where $0 ≤ a_i < 2^{31}$.
Find the maximum result of $a_i XOR a_j$, where 0 ≤ i, j < n.
Could you do this in O(n) runtime?
Example:
1
2
3
4
5
| Input: [3, 10, 5, 25, 2, 8]
Output: 28
Explanation: The maximum result is 5 ^ 25 = 28.
|
分析
题意是给你一个数字的列表，要你找出其中两个 item 进行 XOR 运算所能获得的最大的值。
如果用暴力法，时间复杂度是 $O(n^2)$，而题目要求的复杂度是 $O(n)$。这里有一个需要注意的地方是，因为要得到的是进行异或操作的最大结果，对于一个数而言，要找到与之匹配的，可能能得到异或操作最大值的那个数字有个特点，那就是从高位开始，它的二进制表示与原来的数字要尽可能不同，使用前缀树我们可以实现这样的想法，根据二进制表示构造前缀树，这样进行比较的时候可以尽可能选择与父节点的值相反的子节点，也就是说每次寻找时遵循贪心算法的思路，记录每次异或的结果，得到一个最大值即可，空间复杂度是 $O(n)$，时间复杂度是 $O(n)$。
解决方案1(Java)
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
| class Solution {
public int findMaximumXOR(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
TrieNode root = new TrieNode();
for (int num: nums) {
TrieNode curNode = root;
for (int i = 31; i >= 0; i--) {
int curBit = (num >>> i) & 1;
if (curNode.children[curBit] == null) {
curNode.children[curBit] = new TrieNode();
}
curNode = curNode.children[curBit];
}
}
int max = Integer.MIN_VALUE;
for (int num: nums) {
TrieNode curNode = root;
int curSum = 0;
for (int i = 31; i >= 0; i--) {
int curBit = (num >>> i) & 1;
if (curNode.children[curBit ^ 1] != null) {
curSum += (1 << i);
curNode = curNode.children[curBit ^ 1];
} else {
curNode = curNode.children[curBit];
}
}
max = Math.max(curSum, max);
}
return max;
}
}
class TrieNode {
TrieNode[] children;
public TrieNode() {
children = new TrieNode[2];
}
}
|