421. maximum XOR value of two numbers in the array

Give you an array of integers nums , return nums[i] XOR nums[j] The largest operation result of , among 0 ≤ i ≤ j < n .

Advanced ： You can O(n) Is it time to solve this problem ？

Example 1：

 Input ：nums = [3,10,5,25,2,8]
 Output ：28
 explain ： The maximum result is  5 XOR 25 = 28.

Example 2：

 Input ：nums = [0]
 Output ：0

Example 3：

 Input ：nums = [2,4]
 Output ：6

Example 4：

 Input ：nums = [8,10,2]
 Output ：10

Example 5：

 Input ：nums = [14,70,53,83,49,91,36,80,92,51,66,70]
 Output ：127

Tips ：

1 <= nums.length <= 2 * 104
0 <= nums[i] <= 231 - 1

2. Prefix

struct Trie {
    
    //  Left subtree pointing representation  0  Child nodes of 
    Trie* left = NULL;
    //  The right subtree points to  1  Child nodes of 
    Trie* right = NULL;

    Trie() {
    }
};

class Solution {
    
private:
    //  Root node of dictionary tree 
    Trie* root = new Trie();
    //  The highest bit number is  30
    int C = 30;

public:
    void add(int num) {
    
        Trie* cur = root;
        for (int k = C; k >= 0; k--) {
    
            int bit = (num >> k) & 1;
            if (bit == 0) {
    
                if (cur->left==NULL) {
    
                    cur->left = new Trie();
                }
                cur = cur->left;
            }
            else {
    
                if (cur->right==NULL) {
    
                    cur->right = new Trie();
                }
                cur = cur->right;
            }
        }
    }

    int check(int num) {
    
        Trie* cur = root;
        int x = 0;
        for (int k = C; k >= 0; --k) {
    
            int bit = (num >> k) & 1;
            if (bit == 0) {
    
                // a_i  Of the  k  Binary bits are  0, Should be used to express  1  Child nodes of  right  go 
                if (cur->right) {
    
                    cur = cur->right;
                    x = x * 2 + 1;
                }
                else {
    
                    cur = cur->left;
                    x = x * 2;
                }
            }
            else {
    
                // a_i  Of the  k  Binary bits are  1, Should be used to express  0  Child nodes of  left  go 
                if (cur->left) {
    
                    cur = cur->left;
                    x = x * 2 + 1;
                }
                else {
    
                    cur = cur->right;
                    x = x * 2;
                }
            }
        }
        return x;
    }

    int findMaximumXOR(vector<int>& nums) {
    
        int n = nums.size();
        int x = 0;
        for (int i = 1; i < n; ++i) {
    
            //  take  nums[i-1]  Put in dictionary tree , here  nums[0 .. i-1]  All in the dictionary tree 
            add(nums[i - 1]);
            //  take  nums[i]  regard as  ai, Find the biggest  x  Update answers 
            x = max(x, check(nums[i]));
        }
        return x;
    }
};

1. Hashtable

class Solution {
    

public:
    int findMaximumXOR(vector<int>& nums) {
    
        int x=0;
        // this  31  The binary bits are numbered from low to high  0, 1, ..., 30
        //0,1,⋯,30  We went from the top to the top  30  Start with a binary bit , Determine... In turn  
        //x Every one of you is 0 still 1


        for (int k = 30; k >= 0; k--) {
    
            unordered_set<int> seen;
            //  Will all  pre^k(a_j)  Put it in the hash table 
            for (int num: nums) {
    
                //  If you just want to keep it from the top to the bottom  k  The part that ends with two binary bits 
                //  Just move it to the right  k  position 
                seen.insert(num >> k);
            }

            //  at present  x  From the top to the bottom  k+1  The part that ends with two binary bits 
            //  We will  x  Of the  k  Two binary positions are  1, That is to say  x = x*2+1
            int x_next = x * 2 + 1;
            bool found = false;
            
            //  enumeration  i
            for (int num: nums) {
    
                // or  
                if (seen.count(x_next ^ (num >> k))) {
    
                    found = true;
                    break;
                }
            }

            if (found) {
    
                x = x_next;
            }
            else {
    
                //  If you don't find one that satisfies the equation  a_i  and  a_j, that  x  Of the  k  A binary bit can only be  0
                //  That is to say  x = x*2
                x = x_next - 1;
            }
        }
        return x;
    }
};