Acwing.143 最大异或对(trie树)

题目

在给定的N个整数A1，A2 . …Ax中选出两个进行xor(异或)运算，得到的结果最大是多少?
输入格式
第一行输入一个整数N。
第二行输入N个整数A1~AN。

输出格式

输出一个整数表示答案。

数据范围

1 ≤N ≤105,0≤A<231

• 输入样例:

3
1 2 3

• 输出样例

3

题解

import java.util.Scanner;/*** @author akuya* @create 2023-07-24-0:00*/
public class Mxor {static int N=100010;static int M=31*N;static int n;static int a[]=new int[N];static int son[][]=new int[M][2];static int idx;public static void main(String[] args) {Scanner scanner=new Scanner(System.in);n=scanner.nextInt();int res=0;for(int i=0;i<n;i++){a[i]=scanner.nextInt();}for(int i=0;i<n;i++){insert(a[i]);int t=query(a[i]);res=Math.max(res,a[i]^t);}System.out.println(res);}public static void insert(int x){int p=0;for(int i=30;i>=0;i--){int u=x>>i&1;if(son[p][u]==0) son[p][u]=++idx;p=son[p][u];}}public static int query(int x){int p=0;int res=0;for(int i=30;i>=0;i--){int u=x>>i&1;if(son[p][u^1]!=0){p=son[p][1^u];res=res*2+1^u;}else{p=son[p][u];res=res*2+u;}}return res;}
}

思路

正常遍历时间复杂度为n²，利用trie树存起来，然后分解成二进制遍历。可以压缩时间复杂度到O（n）*O(31)。这样就不会超时了