Given a non-empty array of numbers, a0, a1, a2, … , an-1, where 0 ≤ ai < 231.
Find the maximum result of ai XOR aj, where 0 ≤ i, j < n.
Could you do this in O(n) runtime?
Example:
Input: [3, 10, 5, 25, 2, 8] Output: 28 Explanation: The maximum result is 5 ^ 25 = 28.题目要求O（n）时间复杂度。
因为处理位运算，可以尝试将十进制数转化为二进制数，而二进制数可通过0,1表示，因此可以尝试采用前缀树求解。
首先根据数组元素建立一颗前缀树，这里特别需要注意的一点是：树的深度为33，不是32，因为引入了一个跟节点。当访问nums[i]时，再深入看nums[i]的位信息，如果当前访问到j位，则判断：
1、如果j位只有一个儿子，则别无选择，不论子节点值为0还是1，只能继续往下走。
2、如果j位有两个儿子，说明从该处，至少有两个不同的数出现（含nums[i]），则可以选择与nums[i]在j位不同值的路线走下去
程序如下所示：
class Solution { class TrieNode{ public int val; public TrieNode left; public TrieNode right; public TrieNode(int val){ this.val = val; this.left = null; this.right = null; } } public int findMaximumXOR(int[] nums) { TrieNode root = createTrie(nums); TrieNode curNode = root; int max = 0; for (int i = 0; i < nums.length; ++ i){ curNode = root; int val = 0; for (int j = 31; j >= 0; -- j){ int tmp = nums[i] & (1 << j); if (curNode.left != null && curNode.right != null){ if (tmp == 0){ curNode = curNode.left; } else { curNode = curNode.right; } } else { curNode = curNode.left == null?curNode.right:curNode.left; } val |= (curNode.val << j); } max = Math.max(max, nums[i]^val); } return max; } public TrieNode createTrie(int[] nums){ TrieNode root = new TrieNode(0); TrieNode curNode = root; for (int i = 0; i < nums.length; ++ i){ for (int j = 31; j >= 0; -- j){ int tmp = nums[i] & (1 << j); if (tmp == 0){ if (curNode.right == null){ curNode.right = new TrieNode(0); } curNode = curNode.right; } else { if (curNode.left == null){ curNode.left = new TrieNode(1); } curNode = curNode.left; } } curNode = root; } return root; } }