AcWing 143. 最大异或对_Java含注释
原题链接
简单
作者:
FayunYm
,
2021-01-01 12:19:15
,
所有人可见
,
阅读 357
import java.io.*;
import java.util.Arrays;
public class Main {
//暴力做法为将所有数存入数组,然后外内循环求解最大值,cost=O(n^2)次位运算操作
//若将所有数存入Trie(高位存在前,并且高位为0也要插入),然后尽可能查找与x各位不同的数,高位优先
static final int M =100_001*31;
static int[][] son = new int[M][2];
static int[] val = new int[M]; //记录存储的值,便于求异或值
static int idx; //结点索引值
static void insert(int x) {
int p = 0;
for (int i = 30; i>=0; i--) {
int bit = x >> i & 1; //第i位的值(最右边是第0位)
if (son[p][bit] == 0) {
son[p][bit] = ++idx;
}
p = son[p][bit];
}
val[p] = x;
}
//尽可能查找与x各位不同的数,高位优先。将该数与x求异或并返回
static int find(int x) {
int p = 0;
for (int i = 30; i>=0; i--) {
int bit = x >> i & 1;
int nbit = (bit==0) ? 1 : 0;
if(son[p][nbit] != 0) p = son[p][nbit];
else p=son[p][bit];
}
return val[p] ^ x;
}
public static void main(String[] args) throws IOException{
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter log = new BufferedWriter(new OutputStreamWriter(System.out));
int n = Integer.parseInt(reader.readLine());
String[] s = Arrays.copyOf(reader.readLine().split(" "),n);
int[] number = new int[n];
for(int i = 0; i< n; i++) {
number[i] = Integer.parseInt(s[i]);
insert(number[i]);
}
int ans = 0; //最大异或值
for(var num : number) {
ans = Math.max(ans,find(num));
}
log.write(ans + "");
log.flush();
log.close();
reader.close();
}
}