421. Maximum XOR of Two Numbers in an Array -------M~!!!~!!!!

 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.

 A:

O(n^2)  cause TLE

然后就是自己build Trie (  只需要2个child 。深度固定）

同时，我这里走了一个弯路。  就是build 好了以后，我抛弃了之前的value， 而这样导致一个问题，就是每次分方向的时候， 即使每个parent都有2个child，也要判断4种情况。  

不如直接给定一个值，而去决定往哪个方向go down the Tire.更简洁

class Solution {
public:
    int findMaximumXOR(vector<int>& nums) {
        TrieNode* root = new TrieNode();
        // get the max_xor while building the Trie
        for (auto val : nums) {
            auto p = root;
            for (int i = 31; i >= 0; i--) {
                int mask = 1 << i;
                if (val & mask) {
                    if (not p->one) {
                        TrieNode* tmp = new TrieNode();
                        p->one = tmp;
                    }
                    p = p->one;
                }
                else {
                    if (not p->zero) {
                        TrieNode* tmp = new TrieNode();
                        p->zero = tmp;
                    }
                    p = p->zero;
                }
            }
        }
        int max_xor = 0;
        // to avoid compare 4 possible combination of the Trie p0, p1, we get the max for each value
        for (auto val : nums) {
            auto p = root;
            int cur_max = 0;
            for (int i = 31; i >= 0; i--) {
                int mask = 1 << i;
                if (val & mask) {
                    if (p->zero) {
                        cur_max += mask;
                        p = p->zero;
                    }
                    else {
                        p = p->one;
                    }
                }
                else {
                    if (p->one) {
                        cur_max += mask;
                        p = p->one;
                    }
                    else {
                        p = p->zero;
                    }
                }
            }
            max_xor = max(max_xor, cur_max);
        }
        return max_xor;
    }
private:
    struct TrieNode {
        TrieNode* zero;
        TrieNode* one;
    };
};