AcWing 143. 最大异或对--java详细注解
原题链接
简单
作者:
OneDay1
,
2021-02-26 17:13:32
,
所有人可见
,
阅读 234
import java.util.*;
public class Main{
static int N = 100010,M = 3000000;
static int[] a = new int[N];
//树的长度最多不超过N*31,节点为0,1;
static int[][] son = new int[M][2];
static int n,idx;
// 创建Trie
public static void insert(int a){
int p = 0;
for(int i = 30; i >= 0; i--){
// 判断a的二进制位的第i个数是0还是1;
int s = a >> i & 1;
if(son[p][s] == 0) son[p][s] = ++idx;
p = son[p][s]; //把当前节点移动到下一节点;
}
}
// 查询
public static int query(int a){
int p = 0,res = 0;
for(int i = 30; i >= 0; i--){
//判断数字a在第i位的二进制是0还是1;
int s = a >> i&1;
//要想使得a^x最大,那么x要最小,也就是x得二进制与a二进制相反才行
//判断子节点与当前a中二进制相反得分支存不存在(不存在 son[p][1-s] ==0);
if(son[p][1-s] != 0){
//二进制转十进制操作
//原:3-->110,查:001; index:2、1、0;
//查到一位转换成十进制相加即等于最后与原数异或为最大值
res = res + (1<< i);
//更新p位置,即往下走下一节点(相反得一条路)
p = son[p][1-s];
//查找得分支点没有得话,只能走已存在得分支;
}else p = son[p][s];
}
//返回结果
return res;
}
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int res = 0;
for(int i = 0; i < n; i++){ //初始化数组
a[i] = sc.nextInt();
insert(a[i]);
}
//遍历数组中所有得元素,找到数组中异或得最大得数;
for(int i = 0; i < n; i++){
//query返回得使a[i]^x最大得值
res = Math.max(res,query(a[i]));
}
System.out.println(res);
}
}