leetcode-maximum-xor-of-two-numbers-in-an-array

发表于   |   分类于 ，   |  

题目大意

　　https://leetcode.com/problems/maximum-xor-of-two-numbers-in-an-array/

　　整数数组，找出其中异或值最大的两个数，要求时间复杂度是O(n)

题目分析

　　解法参考：https://discuss.leetcode.com/topic/63213/java-o-n-solution-using-bit-manipulation-and-hashmap/17

　　这里依据了一个异或的性质，就是a^b=c和a^c=b是等价的（因此一种肯定会超时并且正确的方法是从大往小遍历int值，然后第二层循环遍历nums，看nums[i]和int异或后的结果是否在nums中）。我们需要32位逐位考虑。针对每一位，首先根据掩码mask先生成前缀的set，然后再生成到当前位的newMax值，看看set中的值跟newMax结果是否在set中，如果在说明newMax是可取的。注意代码中的mask和max都是累计的，详细可以看下代码解释。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public class Solution {
    public int findMaximumXOR(int[] nums) {
        int mask = 0;
        int max = 0;
        for (int i = 31; i >= 0; i--) {
            mask |= (1 << i); //代表掩码，形式是 111.....
            Set<Integer> set = new HashSet<>(); //mask就是用来求当前位下的所有前缀，存在set里
            for (int n : nums) {
                set.add(mask & n);
            }
            int newMax = max | (1 << i); //newMask代表积累到当前位下可能的最大值
            for (int n : set) {
                if (set.contains(n ^ newMax)) {
                    max = newMax; //找到了，则更新max，留给下次用
                    break;
                }
            }
        }
        return max;
    } 
}

　　复杂度:O(n)