421. Maximum XOR of Two Numbers in an Array (Medium)

Given a non-empty array of numbers, $$a0, a_1, a_2, … , a{n-1},$$ where $$0 ≤ a_i < 2^{31}$$.

Find the maximum result of $$ai$$ XOR $$a_j$$, 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.

Solution 1: Brute Force TLE

Time Complexity: $$O(n^2)$$

class Solution {
public:
    int findMaximumXOR(vector<int>& nums) {
        int res = 0;
        for (int i = 0; i < nums.size(); ++i) {
            for (int j = i+1; j < nums.size(); ++j) {
                res = max((nums[i] ^ nums[j]), res);
            }
        }
        return res;
    }
};

Solution 2: Bit Manipulation 272ms

Time Complexity: $$O(32n)$$

这道题是一道典型的位操作Bit Manipulation的题目，我开始以为异或值最大的两个数一定包括数组的最大值，但是OJ给了另一个例子{10,23,20,18,28}，这个数组的异或最大值是10和20异或，得到30。那么只能另辟蹊径，正确的做法是按位遍历，题目中给定了数字的返回不会超过$$2^{31}$$,那么最多只能有32位，我们用一个从左往右的mask，用来提取数字的前缀，然后将其都存入set中，我们用一个变量t，用来验证当前位为1再或上之前结果res，看结果和set中的前缀异或之后在不在set中，这里用到了一个性质，若a^b=c，那么a=b^c，因为t是我们要验证的当前最大值，所以我们遍历set中的数时，和t异或后的结果仍在set中，说明两个前缀可以异或出t的值，所以我们更新res为t，继续遍历，如果上述讲解不容易理解，那么建议自己带个例子一步一步试试，并把每次循环中set中所有的数字都打印出来，基本应该就能理解了，参见代码如下：

class Solution {
public:
    int findMaximumXOR(vector<int>& nums) {
        int max = 0, mask = 0;

        // search from left to right, find out for each bit is there 
        // two numbers that has different value
        for (int i = 31; i >= 0; i--){
            // mask contains the bits considered so far
            mask |= (1 << i);
            unordered_set<int> t;
            // store prefix of all number with right i bits discarded
            for (int n: nums){
                t.insert(mask & n);
            }

            // now find out if there are two prefix with different i-th bit
            // if there is, the new max should be current max with one 1 bit at i-th position, which is candidate
            // and the two prefix, say A and B, satisfies:
            // A ^ B = candidate
            // so we also have A ^ candidate = B or B ^ candidate = A
            // thus we can use this method to find out if such A and B exists in the set 
            int candidate = max | (1<<i);
            for (int prefix : t){
                if (t.find(prefix ^ candidate) != t.end()){
                    max = candidate;
                    break;
                }

            }
        }
        return max;
    }
};

Solution 3: Trie 59ms

class Solution {
    struct TrieNode {
        TrieNode* children[2];
        TrieNode() {
            for (int i = 0; i < 2; ++i) {
                children[i] = nullptr;
            }
        }
    };
public:
    int findMaximumXOR(vector<int>& nums) {
        TrieNode* root = new TrieNode();
        for (int num: nums) {
            TrieNode* cur = root;
            for (int i = 31; i >= 0; --i) {
                int curBit = (num >> i) & 1;
                if (cur->children[curBit] == nullptr) {
                    cur->children[curBit] = new TrieNode();
                }
                cur = cur->children[curBit];
            }
        }
        int res = 0;

        for (int num: nums) {
            TrieNode* cur = root; // x ^ num: to find cur max
            int curSum = 0;
            for (int i = 31; i >= 0; --i) {
                int curBit = (num >> i) & 1;
                if (cur->children[curBit ^ 1]) {
                    curSum |= (1 << i);
                    cur = cur->children[curBit ^ 1];
                } else {
                    cur = cur->children[curBit];
                }
            }
            res = max(curSum, res);
        }

        return res;

    }
};