很久没有写Leetcode刷题的相关博客了，一来最近比较懒，二来刷的那些题目都不难，没有给我什么新的知识点，就没有写。今天碰到了一个位操作的题，以前这类题目我是不会去碰的，因为不熟悉，但是终究是要接触的。这道题一开始我并没有写出来，提交结果超时，在参考了其他人的解法思路后最终通过。

题目如下：

Given a non-empty array of numbers, a0, a1, a2, … , an-1, where 0 ≤a i< 231.
Find the maximum result of a i XOR a j , where 0 ≤ i, j < n.
Could you do this in O(n) runtime?
Example:

1
2
3
Input: [3, 10, 5, 25, 2, 8]
Output: 28
Explanation: The maximum result is 5 ^ 25 = 28.

题目大意

给定一个非空数组，里面所有数字属于区间(0, 231)。找出这个数组中两两异或的最大值。要求时间复杂度为O(n)

思路

naive solution

最简单的方法当属暴力搜索，两层循环，记录最大的异或值即可，代码比较简单，但是会超时。

1
2
3
4
5
6
7
8
9
public int findMaximumXOR(int[] nums) {
    int result = 0;
    for(int i = 0; i < nums.length; i++){
        for (int j = i + 1; j < nums.length; j ++){
            result = Math.max(nums[i] ^ nums[j]);
        }
    }
    return result;
}

此种解法时间复杂度为O(n2)，空间复杂度为O(1)

better solution

我们还需要用上一个异或的特性，假设a和b产生了最终的答案max，即a ^ b = x，那么根据异或的特性，a ^ x = b。同理，a和b的最高位（前n位）也有相同的性质。

先以最高位为例子，我们可以把所有的数字的最高位放到一个HashSet里面，然后使用1与set里面的所有数字进行异或，如果得出的结果仍然在set里面，那么最终结果的最高位必然为1，否则为0。也即，先假定结果为1，然后与set中所有数字异或，假定a与1异或得到结果b（a ^ 1 = b），而b仍然在set里面，那么说明set中有两个数字异或能得到1（a ^ b = 1）。否则，set中没有两个数字能够异或得到1，那么最终结果的最高位为1的假设失败，说明最终结果的最高位为0。以此类推可以得到第二位、第三位。。。的数字。

再做一下推广，我们将所有数字的前N位放到一个HashSet里面，然后使用之前N-1位得到的最大值前缀prefix与set里面的所有数字进行异或，如果得出的结果仍然在set中，那么第N位必然为1，否则为0。

举个例子，给定数组[14, 11, 7, 2]，二进制表示分别为[1110, 1011, 0111, 0010]。题目说了，数字最长不会超过32位，所以应从i = 31开始，但是所有数字中最多位4位数，简单起见，我直接从最高位i=3开始

1
2
3
4
1. i = 3, set = {1000, 0000} => max = 1000
2. i = 2, set = {1100, 1000, 0100, 0000} => max = 1100
3. i = 1, set = {1110, 1010, 0110, 0010} => max = 1100
4. i = 0, set = {1110, 1011, 0111, 0010} => max = 1100

最终答案是1100 => 12，1011 ^ 0111 = 1100(11 ^ 7 = 12)。

Java版代码如下

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
public int findMaximumXOR(int[] nums) {
    int max = 0;
    int mask = 0;
    for(int i = 31; i >= 0; i --){
        // 为获取前n位的临时变量
        mask = mask | (1 << i);

        HashSet<Integer> set = new HashSet<>();
        for(int num : nums){
        // 将所有数字的前n位放入set中
            set.add(mask & num);
        }
        // 假定第n位为1,前n-1位max为之前迭代求得
        int tmp = max | (1 << i);
        for(int pre : set){
            // 查看`b`是否在
            if(set.contains(tmp ^ pre)){ 
            // b存在，第n位为1
                max = tmp;
                break;
            }
        }                    
    }
    return max;
}

此解法时间复杂度为O(32n)=O(n)，空间复杂度上，我们使用了一个HashSet用于存储所有数字，因此空间复杂度是O(n)。和暴力搜索解法相比，典型的空间换时间。附上AC时间图

提交结果
提交结果

anothor better solution

我以为，上面的解法已经是最佳解法了，结果却发现前面还有一个提交时间小山峰，查看了一下发现有更好的解法，此解法用到了Tries的数据结构。此数据结构我从来之前都没听说过，研究了一下算法后发现，其实Tries类似于二叉树，主要的思路是这样：构建一棵深度为33的二叉树。root节点左孩子为1，右孩子为0代表着所有数字的最高位，其次根据次高位继续往下。如果某一个节点左右子树都不为空，那么得到最终答案的两个数字肯定分别出自于左右子树且此位为1；如果任意一个为空，那么最终答案该位为0，依次迭代得到最终结果。对此解法我并没有详细研究，感兴趣的可以自己去看看
Java O(n) solution using Trie

cheat solution

是的，通过查看时间表我发现了一个作弊的答案。

此题一共29个测试用例，最后一个测试用例是用来测试时间复杂度的，长度是20000。超时的原因就是因为这最后一个测试用例，因此有答案直接对此做了特殊处理，然后使用暴力解法……最后只用时15ms

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int findMaximumXOR(int[] nums) {
    if(nums.length == 20000){
        return 2147483644;
    }
    long max = 0;
    for (int i = 0; i < nums.length; i++) {
        for (int j = i+1; j < nums.length; j++) {
            long xor = nums[i] ^ nums[j];
            if (xor > max) {
                max = xor;
            }
        }
    }
    return (int) max;
}

可怕的人类！