题目描述

给定一组数组，然后随意两个异或，找到最大的输出。

输入样例

3
1 2 3

输出样例

3

算法1

(trie数) $O(nlogn)$

思路
    1. 首先暴力的做法就是两层for循环，第一层就是遍历整个数组，第二层就是让他们异或，找到最大
    2. 如果优化？
        - 数组的二进制表示形式最长31位，然后找异或最大的，比如我们要找1000 0000 0000 0000 0000 0000 0000 0000 
        是不是应该先找高位30位（0开始）是1相反的是0，异或是1，肯定是比与1异或等于0是大的,因为高位是1肯定比
        高位是0的大，所以我们可以依次找，类似于一个树，如果没有相反的就用有的值，这样我们就可以用trie解决 

时间复杂度：$O(nlogn)$

参考文献：y总

Java 代码

import java.util.Scanner;

public class Main {
    static int N = 100010;
    static int M = 31 * N;// 最大节点数
    static int[][] son = new int[M][2];
    static int idx;
    static int[] a = new int[N];

    static void insert(int x){// 拆入节点
        int p = 0;// 从根节点开始
        for (int i = 30; i >= 0; i--){
            int u = x >> i & 1;// 求二进制中第i的值
            if (son[p][u] == 0) son[p][u] = ++idx;// 插入当前节点
            p = son[p][u];// 获取当前节点
        }
    }

    static int query(int x){
        int p = 0;// 从根节点开始
        int res = 0;
        for (int i = 30; i >= 0; i--){
            int u = x >> i & 1;// x的二进制表示的第i位的值
            if (son[p][u ^ 1] != 0){// 当前位的值的相反位 存在
                p = son[p][u ^ 1];
                res = res * 2 + u ^ 1;
            }else {
                p = son[p][u];
                res = res * 2 + u;
            }
        }
        return res;
    }

    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        int n = Integer.parseInt(scan.nextLine());
        String[] s = scan.nextLine().split(" ");
        for (int i = 0; i < n; i++) {
            a[i] = Integer.parseInt(s[i]);
        }

        int res = 0;// 存储结果  最小是0
        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);
        scan.close();
    }
}