421. Maximum XOR of Two Numbers in an Array

Given anon-emptyarray of numbers, a0, a1, a2, … , an-1, where 0 ≤ ai< 2^31.

Find the maximum result of aiXOR 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.

S: bit manipulation O(n)

要找到最大的xor结果，数字最多有30位，可以从最高位开始尝试看看是否有两数在此位不同。

由高位到低位构建prefix，每次尝试将第i位置1

    int findMaximumXOR(vector<int>& nums) {
        int mask = 0, result = 0;
        for (int i = 30; i >= 0; i--) {
            mask |= 1 << i;
            unordered_set<int> prefix;
            for (int num : nums) prefix.insert(num & mask); //得到每个数字的前i位

            int potentialMax = result | (1 << i);
            //查找是否存在A ^ B = potentialMax => A ^ potentialMax = B
            //若存在则更新result
            for (int pre : prefix) {
                if (prefix.find(pre ^ potentialMax) != prefix.end()) {
                    result = potentialMax;
                    break;
                }
            }
        }
        return result;
    }