MaximumXORofTwoNumbersinanArray

421. Maximum XOR of Two Numbers in an Array

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

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 &＃61; 28.

我的代码

class Solution {public int findMaximumXOR(int[] nums) {if (nums.length &＃61;&＃61; 0) {return 0;}TrieNode root &＃61; new TrieNode();// 建树// 每一个数字循环32次&＃xff0c;反正输入没有负数// 从最高位开始处理for (int i : nums) {TrieNode node &＃61; root;for (int j &＃61; 31; j >&＃61; 0; j--) {int bit &＃61; (i >> j) & 1;if (bit &＃61;&＃61; 1) {if (node.one &＃61;&＃61; null) {// one的位置是null&＃xff0c;就新建node.one &＃61; new TrieNode();}node &＃61; node.one;} else {if (node.zero &＃61;&＃61; null) {node.zero &＃61; new TrieNode();}node &＃61; node.zero;}}}int max &＃61; Integer.MIN_VALUE;//找每一个数字和别的数字异或出来的最大值&＃xff01;//所有最大值&＃xff0c;取其中最大的for (int i : nums) {TrieNode node &＃61; root;int XOR &＃61; 0;// 异或结果,的累加。按位累加也是牛逼for (int j &＃61; 31; j >&＃61; 0; j--) {int bit &＃61; (i >> j) & 1;//如果这一位是1&＃xff0c;为了异或最大&＃xff0c;最好使用0&＃xff0c;这样异或出来是1//如果0不存在就只能使用1&＃xff0c;这样这一位异或出来就是0//如果这一位是0&＃xff0c;为了异或最大&＃xff0c;最好使用1&＃xff0c;这样异或出来是1//如果1不存在就只能使用0&＃xff0c;这样这一位异或出来就是0if (bit &＃61;&＃61; 1) {if (node.zero !&＃61; null) {node &＃61; node.zero;XOR &＃43;&＃61; 1 < XOR ? max : XOR;}return max;}
}class TrieNode {TrieNode zero;TrieNode one;
}


同样思路
trick: 通过预处理得到最大值的首位1&＃xff0c;优化了Trie树的深度。

class Solution {TreeNode root &＃61; new TreeNode(0);public int findMaximumXOR(int[] nums) {int max &＃61; findMax(nums);int maxBit &＃61; 32 - Integer.numberOfLeadingZeros(max);//build prefix treeTreeNode currNode &＃61; root;for (int i &＃61; 0; i &＃61;0 ; j--) {int tmp &＃61; (nums[i] >>j)& 1;if(tmp &＃61;&＃61; 0){if(currNode.left &＃61;&＃61; null){currNode.left &＃61; new TreeNode(0);}currNode &＃61; currNode.left;}else {if(currNode.right &＃61;&＃61; null){currNode.right &＃61; new TreeNode(1);}currNode &＃61; currNode.right;}}// finished for nums[i], will do it for nums[i&＃43;&＃43;];currNode &＃61; root;}//find max xor valueint maxXOR &＃61; 0;for (int i &＃61; 0; i &＃61;0; j--) {int tmp &＃61; (nums[i] >>j)& 1;if(currNode.left !&＃61; null && currNode.right !&＃61; null){if(tmp &＃61;&＃61; 0){currNode &＃61; currNode.right;}else {currNode &＃61; currNode.left;}}else {currNode &＃61; currNode.left &＃61;&＃61; null ? currNode.right : currNode.left;}res &＃43;&＃61; (tmp^currNode.val) < res ? maxXOR : res;}return maxXOR;}private int findMax(int[] nums){int max &＃61; nums[0];for (int i &＃61; 1; i max){max &＃61; nums[i];}}return max;}private static class TreeNode{int val;TreeNode left,right;TreeNode(int val){this.val &＃61; val;}}
}


Bit maniputaipon
这个解法也是利用前缀树的思想&＃xff0c;利用Map保存下一次遍历的前缀。&＃xff08;空间换时间&＃xff09;
贪心思想&＃xff0c;从最大的bit到最小的bit组装最大异或值。
借用一段解释&＃xff1a;
I think most people who find it hard to understand the code is stuck on this line if(set.contains(tmp ^ prefix))
The tricky part here is that we need to be aware of a key property of XOR applying on the above line: if A ^ B &＃61; C, then A ^ B ^ B &＃61; C ^ B, then A &＃61; C ^ B
Before executing that line, max stands for the maximum we can get if we consider only the most significant i - 1 bits, tmp stands for the potential max value we can get when considering the most significant i bits. How can we get this tmp? The only way we can get this value is that we have two values A and B in the set (a set of most significant i bits of each member), such that A ^ B equals to tmp. As mentioned earlier, A ^ B &＃61; tmp is equivalent to A &＃61; tmp ^ B. Here is where that line comes in: set.contains(tmp ^ B).

public class Solution {public int findMaximumXOR(int[] nums) {int max &＃61; 0, mask &＃61; 0;for(int i &＃61; 31; i >&＃61; 0; i--){mask &＃61; mask | (1 < set &＃61; new HashSet<>();for(int num : nums){set.add(num & mask);}int tmp &＃61; max | (1 <}