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

分析

这道题要求我们找出一个数组中两个数产生的最大的XOR值，并且要求在O(n)的时间复杂度内完成。

如果没有最后一条限制，那么这道题还是挺简单的，不过此题来自微软的面试，那么最容易想到的O(n*2)的解法肯定是无法拿到offer的。

我们知道，要找到这个最大的异或值，应该让两个数在对应位上的差距尽可能大，所以我们要先把组成一个数的各个位取出来，之后我们假设有一个候选最大值candidate，下一步要做的是确认数组中的某两个数可以在经过XOR之后得到这个candidate。

这里就是这道题的精髓部分，我们需要利用异或操作的性质:

如果A^B==C
那么B^C==A,或A^C==B

所以我们要想证明这个candidate确实是由数组中的两个数XOR后得到的，只需要把candidate看成C，把数组中的两个数看做A和B，之后遍历之前得到的各个二进制位并且与candidate进行XOR，如果异或的结果与之前获得的二进制位中的某个值相同，则说明candidate是由数组中的两个数做XOR得到的。

这里就存在一个问题，我们之前得到的二进制位如果保存在数组里，反复查找就显得很浪费时间了，所以我们用一个hash-table来降低查找操作上的时间开销。

代码如下：

class Solution {
public:
    int findMaximumXOR(vector<int>& nums) {
        int maxValue=0,mask=0;
        unordered_set<int> map;
        for(int i=31;i>=0;i--){
            mask|=(1<<i);
            map.clear();
            for(int num:nums)
                map.insert(num&mask);
            int candidate= maxValue|(1<<i);
            for(int prefix:map){
                if(map.find(prefix^candidate)!=map.end()){
                    maxValue=candidate;
                    break;
                }
            }
        }
        return maxValue;
    }
};

这道题还有利用字典树和递归的两种解法，不过我还没有完全理解这两种算法。

• [Trie and recursion ]