在给定的N个整数A1A2ANA1,A2……AN中选出两个进行xor(异或)运算,得到的结果最大是多少?

输入格式

第一行输入一个整数N。

第二行输入N个整数A1A1~ANAN。

输出格式

输出一个整数表示答案。

数据范围

1N1051≤N≤105,
0Ai<2310≤Ai<231

输入样例:

3
1 2 3

输出样例:

3

思路:
    每个数散成二进制存进tire树里边,找能和当前二进制xor成1的最大数字取最大值,只需要从跟走到叶节点就可以找到和当前数字最大的数了,这样的话每个数字最多走31位也就是总共的次数最多是31*100000,所以时间复杂度相当于nlogn

  



#include<iostream>

using namespace std;
//int 单个整数最大二进制是31个1,tire存储的每个分支数最多有31个节点
const int N = 1e5+10,M = 31*N;

int n;
int a[N];
//每个节点有01两种情况所以是2
int son[M][2],idx;

void insert(int x){
    int p = 0;
    for(int i = 30;i >= 0;i--)
    {
        //取第i位的二进制数是什么东西
        int u = x >> i & 1;
        if(!son[p][u]) son[p][u] = ++idx;
        p = son[p][u];
    }
}

int query(int x){
    int p = 0,res = 0;
    for(int i = 30;i >= 0;i--){
        int u = x >> i & 1;
        if(son[p][!u]){
            p = son[p][!u];
            res = res * 2 + !u;

        } else{
            p = son[p][u];
            res = res * 2 + u;
        }
    }
    return res;
}
int main(){
    cin >> n;
    for(int i = 0;i < n;i++) cin >> a[i];

    int res = 0;
    //先插入,少一个判空的条件,所以先插入
    for(int i = 0;i < n;i++){
        insert(a[i]);
        int t = query(a[i]);
        res = max(res,a[i] ^ t);
    }

    cout << res;


}

  

01-14 13:26