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;

    }