leetcode421-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.

现有一个非空的整数数组，问如何能够找出整数数组中两个整数的异或结果的最大值。

思路和代码

这里解释一下高分答案贪婪算法的思路。每一次我们都试图假设第 i 位的异或结果为 1，并且判断是否能够从数组中找到任意两个整数，其在该位上的异或值为 1。如果找不到，则说明任意两个整数在该位的异或结果只能是 0。接着对第 i - 1 位进行同样的判断。从高位开始的原因在于，从贪婪角度的算法看来，我们更希望高位为 1，其生成的异或值更大。

代码如下：

    public int findMaximumXOR(int[] nums) {
        //32 位到第 i 位为止算出的异或最大值
        int maxResult = 0;
        int mask = 0;
        for(int i = 31 ; i>=0 ; i--) {
            //i~32 位全为 1
            mask |= (1 << i);
            Set<Integer> set = new HashSet<>();
            // 取所有整数的前 32- i 位的结果并保存
            for(int num : nums) {set.add(num | mask);
            }
            
            // 假设第 i 位能够异或出结果 1
            int greedyTry = maxResult | (1 << i);
            // 使用结论 a^b=c, 则 a^c=b。根据该结论，我们假设整数数组中的两个整数在第 i 为的值为 1，且 set 中存储了所有的 a 的值，异或出 b 的值后看 b 是否也在 set 中。for(int num : set) {if(set.contains(greedyTry ^ num)) {
                    maxResult = greedyTry;
                    break;
                }
            }
        }
        return maxResult;

    }