【題解】LeetCode 421. Maximum XOR of Two Numbers in an Array

class Solution {
public:
    int a[650000][2] = {}, idx = 0;
    int findMaximumXOR(vector<int>& nums) {
        int mx = 0;
        int n2 = 0;
        for (int j = 30; j >= 0; j--){
            if ((nums[0])&(1<<j)){
                if (!a[n2][1]){
                    idx++;
                    a[n2][1] = idx;
                }
                n2 = a[n2][1];
            }
            else{
                if (!a[n2][0]){
                    idx++;
                    a[n2][0] = idx;
                }
                n2 = a[n2][0];
            }
        }
        for (int i = 1; i < nums.size(); i++){
            int n1 = 0, n2 = 0, ans = 0;
            for (int j = 30; j >= 0; j--){
                if ((nums[i])&(1<<j)){
                    if (a[n1][0]){
                        n1 = a[n1][0];
                        ans |= (1<<j);
                    }
                    else n1 = a[n1][1];
                    if (!a[n2][1]){
                        idx++;
                        a[n2][1] = idx;
                    }
                    n2 = a[n2][1];
                }
                else{
                    if (a[n1][1]){
                        n1 = a[n1][1];
                        ans |= (1<<j);
                    }
                    else n1 = a[n1][0];
                    if (!a[n2][0]){
                        idx++;
                        a[n2][0] = idx;
                    }
                    n2 = a[n2][0];
                }
            }
            mx = max(mx, ans);
        }
        return mx;
    }
};