[Leetcode-421] Maximum XOR of Two Number in an Array?
Given a non-empty array of numbers, a0, a1, a2, ..., an-1, where 0 <= ai <= 2^31.
Find the maximum result of ai XOR aj, where 0 <=i, j < n.
Do it in O(n) runtime.
Input: [3, 10, 5, 25, 2, 8]
Output: 28
Explanation: The maximum result is 5 ^ 25 = 28.
一个数组中取 两个数异或 的最大值。
解析
遍历数组，对每个数的二进制构建一棵字典树。
再次遍历数组，对每个数的每个二进制位与1异或：数组元素的二进制位为0，则寻找到值为1的子树，数组元素的二进制位为1，则寻找到值为0的子树。(当然也可以与0异或)
与1异或后子树不为空，则可计数并累加；与1异或后子树为空，则继续向下查找。
划重点！！！
- 对数组元素的二进制构建Trie树。
- 寻找子树的时候，与1(或0)异或。
public class Solution {
public int findMaximumXOR(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
TrieNode root = new TrieNode();
// To build Trie Tree.
for (int num : nums) {
TrieNode node = root;
for (int i = 31; i >= 0; i--) {
int curbit = (num >>> i) & 1;
if (node.children[curbit] == null) {
node.children[curbit] = new TrieNode();
}
node = node.children[curbit];
}
}
int max = Integer.MIN_VALUE;
// To find maximum XOR value.
for (int num : nums) {
TrieNode node = root; // All num start from root node to find。
int curMax = 0;
for (int i = 31; i >= 0; i--) {
int curbit = (num >>> i) & 1;
if (node.children[curbit ^ 1] != null) {
curMax += (1 << i);
node = node.children[curbit ^ 1];
} else {
node = node.children[curbit];
}
}
max = curMax > max ? curMax : max;
}
return max;
}
/**
* 构建 TrieNode。
*/
class TrieNode {
TrieNode[] children;
public TrieNode() {
children = new TrieNode();
}
}
}
[完]
