421. 数组中两个数的最大异或值

给你一个整数数组 nums ，返回 nums[i] XOR nums[j] 的最大运算结果，其中 0 ≤ i ≤ j < n 。

---

复杂度：O(N)
思路：用Set记录不同长度的二进制串，结果为ans，我们希望ans越大越好，即最新位为1，对于每一个数字a，进行ans^a操作，看看能不能找到b，能找到，则为a，不能找到，则为a-1。

class Solution {
    public int findMaximumXOR(int[] nums) {
        int maxBit = 30;
        int x = 0;
        for(int k=maxBit; k>=0; k--) {
            Set<Integer> set = new HashSet();
            for(int num:nums) {
                // 记录相应的二进制串
                set.add(num>>k);
            }
            int nextX = x*2 + 1;
            boolean found = false;
            for(int num:nums) {
                if(set.contains((num>>k)^nextX)) {
                    found = true;
                }
            }
            if(found) {
                x = nextX;
            } else {
                x = nextX-1;
            }
        }
        return x;

    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27