思路1 暴力 O(N^2)
依次计算Ai和Aj的异或值,取最大,因为本题的N=10^5,故会超时
思路2 贪心&Trie树
贪心:根据异或运算的性质,可以发现,两个数的第i位如果是不相等的,如一个是0,一个是1,那么异或的结果是1,而且1的值在高位的话,这两个数异或的结果越大。
Trie树:如何避免过多的异或计算,故想到Trie树去存储每一个数字的情况
import java.util.Scanner;
public class Main {
static int MAX_N = 32 * 100010; // 本题的Ai范围是[0, 2^31 - 1],因为int是4字节,第32位是符号位,所以都是0,异或的结果也都是0,也可以开成31 * 10010
static int[][] son = new int[MAX_N][2]; // 每一个数最多32位,N = 100000,所以一共需要这么多个数组元素去存储
static int idx = 0; // idx表示当前可以使用的存储下标,0表示Trie树中无元素,这是用数组去模拟树型结构
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int max = 0;
for (int i = 0; i < N; i++) {
int val = sc.nextInt();
if (i == 0) { // 第一次读进来的元素,没有和其异或的值,故只插入
insert(val);
}
max = Math.max(max, query(val)); // 查询与其异或的最大值
insert(val);
}
System.out.print(max);
}
private static void insert(int val) {
int par = 0;
for (int i = 31; i >= 0; i--) {
int bit = (val >> i) & 1;
if (son[par][bit] == 0) son[par][bit] = ++idx;
par = son[par][bit];
}
}
private static int query(int val) {
int par = 0, ret = 0; // par=0 表示第一位 注意和idx的区别,idx用来模拟树型存储
for (int i = 31; i >= 0; i--) { // 贪心计算 从高位开始
int bit = (val >> i) & 1;
int tmp = bit == 0 ? 1 : 0; // Java中取反操作 0变1 1变0
if (son[par][tmp] != 0) { // 如果有与其相反的位
par = son[par][tmp]; // 按照异或为1的情况去搜索下一位的节点位置
ret = (ret << 1) + 1; // 边贪心边计算最后异或的值,<<1相当于*2, +1表示异或值是1
} else { // 找不到与其相反的位
par = son[par][bit]; // 按照异或为0的情况去搜索下一位的节点位置
ret = (ret << 1) + 0; // 边贪心边计算最后异或的值,<<1相当于*2, +0表示异或值是0
}
}
return ret;
}
}