在给定的N个整数A1,A2……ANA1,A2……AN中选出两个进行xor(异或)运算,得到的结果最大是多少?
输入格式
第一行输入一个整数N。
第二行输入N个整数A1A1~ANAN。
输出格式
输出一个整数表示答案。
数据范围
1≤N≤1051≤N≤105,
0≤Ai<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; }