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 < 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.
含义：给定一个非空数组，任意两个整数做异或操作，找到最大的异或值
1 public int findMaximumXOR(int[] nums) { 2 int max = 0, mask = 0; 3 // test each bit pose, 判断能不能构成所需要的值； 4 for(int i = 31; i >= 0; i --) { 5 // 每次都在之前的基础上更新mask 6 mask = mask | (1 << i); //用来累加获取每个数的前N位 7 Set<Integer> set = new HashSet<>(); 8 for(int num : nums) { 9 // add the number which has the mask as its prefix; 10 set.add(num & mask); 11 } 12 // 假设当前所能达到的最大值是这个temp值； 13 int tmp = max | (1 << i);//用来获取最大值的前N位 14 for(Integer prefix : set) { 15 // 利用了 ^ 的 prefix ^ tmp = c，则 prefix ^ c = temp 16 if(set.contains(prefix ^ tmp)) { 17 // 如果能组成就直接break 18 max = tmp; 19 break; 20 } 21 } 22 } 23 return max; 24 }