leetcode：421. The maximum XOR value of two numbers in the array

Title source

• leetcode：421. The maximum exclusive or value of two numbers in an array

Title Description

class Solution {
    
public:
    int findMaximumXOR(vector<int>& nums) {
    

    }
};

title

because 1<=nums.length < $2\ast 10^4$, Because the number of instructions is the largest $10^8$

• If the time complexity of the algorithm is O(N^2), Then the number of instructions 4 * 10^8, Then it will time out
• That is, you must use O(N) perhaps O(N*logN) The algorithm of

What shall I do? ？ You can use the prefix number method , See the specific analysis Algorithm ： The largest subarray XOR and , The only difference between them is that XOR and are added to the prefix tree , Here we add the array directly to the structure

#include <memory>
struct TrieNode {
    
    std::vector<std::shared_ptr<TrieNode>> next;
    explicit TrieNode() : next(2, NULL){
    
    }
};

class NumTrie{
    
    std::shared_ptr<TrieNode> head = std::make_shared<TrieNode>();
public:
    void add(int num){
    
        auto curr = head;
        for (int i = 31; i >= 0; --i) {
    
            int path = (num >> i) & 1;
            curr->next[path] = curr->next[path] == nullptr ?   std::make_shared<TrieNode>() : curr->next[path];
            curr = curr->next[path];
        }
    }

    int maxXor(int num){
    
        int ans = 0;
        auto curr = head;
        for (int i = 31; i >= 0; --i){
    
            int path = (num >> i) & 1;
            int best = i == 31 ? path : path ^ 1;
            best = curr->next[best] == nullptr ? best ^ 1 : best;
            curr = curr->next[best];
            ans |= ((path ^ best) << i);
        }
        return ans;
    }
};
class Solution {
    
public:
    int findMaximumXOR(vector<int>& nums) {
    
        if(nums.empty()){
    
            return 0;
        }

        // 0 ≤ i ≤ j < n
        int max = INT32_MIN;
        NumTrie numTrie;
        for (int num : nums) {
    
            numTrie.add(num);
            max = std::max(max, numTrie.maxXor(num));
        }
        return max;
    }
};