421 Maximum XOR of Two Numbers in an Array

1. Question

Given a non-empty array of numbers, a0, a1, a2, … , an-1, where 0 ≤ ai< 231.
Find the maximum result of aiXOR aj, where 0 ≤i,j<n.
Could you do this in O(n) runtime?
Example:
1
Input: [3, 10, 5, 25, 2, 8]
2
3
Output: 28
4
5
Explanation: The maximum result is 5 ^ 25 = 28.
Copied!

2. Implementation

(1) Brute Force
1
class Solution {
2
public int findMaximumXOR(int[] nums) {
3
if (nums == null || nums.length == 0) {
4
return 0;
5
}
6
7
int max = 0;
8
9
for (int i = 0; i < nums.length; i++) {
10
for (int j = i + 1; j < nums.length; j++) {
11
max = Math.max(max, nums[i] ^ nums[j]);
12
}
13
}
14
return max;
15
}
16
}
Copied!
(2) Bit Manipulation + Trie
1
class Solution {
2
class TrieNode {
3
TrieNode[] childNode;
4
5
public TrieNode() {
6
childNode = new TrieNode[2];
7
}
8
}
9
10
class Trie {
11
TrieNode root;
12
13
public Trie() {
14
root = new TrieNode();
15
}
16
17
public void insert(int num) {
18
TrieNode curNode = root;
19
for (int i = 31; i >= 0; i--) {
20
int bit = (num >>> i) & 1;
21
22
if (curNode.childNode[bit] == null) {
23
curNode.childNode[bit] = new TrieNode();
24
}
25
curNode = curNode.childNode[bit];
26
}
27
}
28
}
29
30
public int findMaximumXOR(int[] nums) {
31
if (nums == null || nums.length == 0) {
32
return 0;
33
}
34
35
Trie trie = new Trie();
36
37
for (int num : nums) {
38
trie.insert(num);
39
}
40
41
int max = 0;
42
43
for (int num : nums) {
44
int curSum = 0;
45
TrieNode curNode = trie.root;
46
47
for (int i = 31; i >= 0; i--) {
48
int bit = (num >>> i) & 1;
49
50
if (curNode.childNode[bit ^ 1] != null) {
51
curSum |= (1 << i);
52
curNode = curNode.childNode[bit ^ 1];
53
}
54
else {
55
curNode = curNode.childNode[bit];
56
}
57
}
58
59
max = Math.max(max, curSum);
60
}
61
return max;
62
}
63
}
Copied!

3. Time & Space Complexity

Brute Force: 时间复杂度O(n^2), 空间复杂度O(1)
Bit Manipulation + Trie: 时间复杂度O(n), 空间复杂度O(n)