题目描述

最大异或对

JAVA 代码

import java.util.*;
import java.io.*;

class Main{
    static int N = 100000, M = 3000000, idx = 0;
    static int[][] son = new int[M][2];
    static int[] a = new int [N];

    //插入模板
    static void insert(int x){
        //p为父节点
        int p = 0;
        //31 位, i >= 0, 一共执行31次
        for(int i = 30; i>= 0; i--){
            //trie树 左移i位是否是1, 如果没此节点则创建.
            if(son[p][x >> i & 1] == 0)
                son[p][x >> i & 1] = ++ idx;
            //更新父节点为子节点
            p = son[p][x >> i & 1];
        }
    }
    static int query(int x){
        int p = 0, res = 0;
        for (int i = 30; i>=0; i--){
            //左移i为是否为1;
            int s = x >> i & 1;
            //异或数
            int sp = s == 0 ? 1 : 0;
            //如果有异或数
            if(son[p][sp] != 0){
                //则这一位上的异或数为1;
                //末尾加1, 往左移i位.
                res += 1 << i;
                //更新为异或数
                p = son[p][sp];
            }else{
                //没有异或数则更新原数字的子节点.
                p = son[p][s];
            }
        }
        return res;
    }

    public static void main(String args[])throws IOException{
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(in.readLine());
        a = Arrays.asList(in.readLine().split(" ")).stream().mapToInt(Integer::parseInt).toArray();

        for (int i =0; i < n; i++){
            insert(a[i]);
        }

        int res = 0;
        for (int i =0; i< n; i++){
            res = Math.max(res, query(a[i]));
        }
        System.out.print(res);
    }
}