最大异或对

• ①. 题目
• ②. 思路
• ③. 学习点
• ④. 代码实现

原题链接

①. 题目

②. 思路

• 这题可以用暴力破解， 但是可以使用Trie树进行优化，先将所有的数的二进制存放到Trim树中，在遍历每一个树的二进制，在Trie树中判断，因为是异或运算，相同为0，相异为1，为了求最大的值，我们优先考虑相反，若trim树中存在与正在遍历的树相应位置的二进制值相反就取那个值，并走这个值的子树，若不存在相反的二进制数，只能继续遍历，取值是0，再走这个数的子树反复比较，求出最大值，对于A的范围最大在2^31，我们只需要遍历31次，最终时间复杂度在O(N)*31

③. 学习点

Trie树

④. 代码实现

import java.util.*;

public class Main {
	
	static int N=100010,M=N*31; //一共是N个数字，每个数字循环31次 =N*31
	static int[][] trim=new int[M][2];  //当前节点的子节点,第一维表示trie的长度,第二维表示每个节点只会有两个子节点
	static int idx=1,res=0; //从1开始存储
	
	public static void insert(int a) {
		int p=0; //当前节点
		for(int i=30;i>=0;i--) {
			int temp=a>>i&1;  //判断该位是不是1
			if(trim[p][temp]==0) { //若该位置是空的创建新的位置
				trim[p][temp]=idx++;
			}
			p=trim[p][temp]; //若是存在，直接跳到下一个节点
		}
	}
	
	public static int query(int a) {
		int p=0,res1=0;
		for (int i=30;i>=0; i--) {
			int temp=a>>i&1;
			if(trim[p][1-temp]!=0) { //这里是若相反位存在，则加上结果,并且走到下一个节点
				res1+=(1<<i);
				p=trim[p][1-temp];
			}else {  //若不存在，直接跳到下一个节点
				p=trim[p][temp];
			}
		}
		return res1;
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int[] arr=new int[N];
		for(int i=0;i<n;i++) {
			arr[i]=sc.nextInt();
			insert(arr[i]);
		}
		for (int i = 0; i <n; i++) {
			res=Math.max(res, query(arr[i]));
		}
		System.out.println(res);
	}

}