最大异或对
在给定的 N 个整数 A1,A2……AN 中选出两个进行 xor(异或)运算,得到的结果最大是多少?
输入格式
第一行输入一个整数 N。
第二行输入 N 个整数 A1~AN。
输出格式
输出一个整数表示答案。
数据范围
1≤N≤ 1 0 5 10^5 105,
0≤Ai< 2 31 2^{31} 231
输入样例:
3
1 2 3
输出样例:
3
【思路分析】
字典树(TrieTree),是一种树形结构,典型应用是用于统计,排序和保存大量的字符串(但不仅限于字符串,如01字典树)。主要思想是利用字符串的公共前缀来节约存储空间。很好地利用了串的公共前缀,节约了存储空间。字典树主要包含两种操作,插入和查找。
比如,我们要存储2(010)、4(100)、3(011)、6(110)、5(101)的二进制
这样我们要进行查找最大异或对时,无需进行二重循环,只需要枚举每个数,然后每个数按照从高位到低位找不同位的值,例如找与2(010)异或最大的值,从高位到低位
第一次寻找,2的最高位是0,寻找字典树中根节点的右孩子是否存在,存在则结果加上 2 2 2^2 22
第二次寻找,2的次高位是1,寻找第一次寻找结点的左孩子是否存在,存在则结果加上 2 1 2^1 21
第三次寻找,2的最低位是0,寻找第二次寻找到结点的右孩子是否存在,存在则结果加上 2 0 2^0 20
最终异或后的结果是7(111)
而对于寻找,则需要知道每次结点的编号,因此在插入的时候,不妨记录每个结点的编号
import java.io.*;
import java.util.*;
public class Main {static final int N = 100010;static final int M = 3000010;//id是结点编号static int id = 0;static int[] arr = new int[N];static int[][] trie = new int[M][2];public static void main(String[] args) throws Exception {BufferedReader br = new BufferedReader(new InputStreamReader(System.in));String row1 = br.readLine();int n = Integer.parseInt(row1);String row2 = br.readLine();String[] num = row2.split(" ");for(int i = 0; i < n; i++) {arr[i] = Integer.parseInt(num[i]);insert(arr[i]);}int res = 0;for(int i = 0; i < n; i++) {res = Math.max(res, query(arr[i]));}System.out.println(res);br.close();}//构建字典树public static void insert(int x) {int k = 0;for(int i = 30; i >= 0; i--) {int bit = x >> i & 1;if(trie[k][bit] == 0) {trie[k][bit] = ++id;}k = trie[k][bit];}}public static int query(int x) {int k = 0, res = 0;for(int i = 30; i >= 0; i--) {int bit = x >> i & 1;//这一位能找到用来异或的数if(trie[k][bit ^ 1] != 0) {res += 1 << i;k = trie[k][bit ^ 1];} else{k = trie[k][bit];}}return res;}
}