题目描述

给定一个非空数组，数组中元素为 a0, a1, a2, … , an-1，其中 0 ≤ ai < $2^{31}$。

找到 ai 和aj 最大的异或 (XOR) 运算结果，其中0 ≤ i,  j < n 。

在O(n)的时间解决这个问题

样例

输入: [3, 10, 5, 25, 2, 8]

输出: 28

解释: 最大的结果是 5 ^ 25 = 28.

算法

(贪心 + Trie树)

时间复杂度： $O(n)$
思想：将每个数字的二进制位，从高位到低位存储到前缀树中，也就是说前缀树中仅有0和1这两个数字。

• 根据数学知识可以知道：$2^i$ > $2^{i-1}$+$2^{i-2}$+…+$2^1$+$2^0$
• 可以发现：异或只要两位不相同就是1，如果高位有一位是1，那么数就会大于这一位是0且低位全是1的情况。这就是从高位开始遍历的贪心思想。
• 如果某一位二进制位是0，但是前缀树的遍历过程中没有1的分支，则被迫走0的分支，反过来同理
• 树的高度由二进制位最多的数字决定，所以分支非0即1，不会有某一个数的二进制位先走到底的情况

以样例[3, 10, 5, 25, 2, 8]为例，图示如下

Java 代码

• 先遍历一遍所有整数，把所有二进制位建树
• 再遍历一遍所有整数，尽可能将每个整数的尽可能相反的二进制位从树中找到，并且记录下每一轮循环的最大异或值

class Solution {
    class Node{
        Node[] son = new Node[2];
    }
    Node root = new Node();
    void insert(int x){
        Node p = root;
        for(int i = 30; i >= 0; i--){
            int t = (x >> i) & 1;
            if(p.son[t] == null){
                p.son[t] = new Node();
            }
            p = p.son[t];
        }
    }

    int search(int x){
        Node p = root;
        int xor = 0;
        for(int i = 30; i >= 0; i--){
            int t = (x >> i) & 1;
            if(t == 0 && p.son[1] != null){
                xor += (1 << i);
                p = p.son[1];
            }else if(t == 1 && p.son[0] != null){
                xor += (1 << i);
                p = p.son[0];
            }else{
                p = p.son[t];
            }
        }
        return xor;
    }

    public int findMaximumXOR(int[] nums) {
        if(nums.length == 0) return 0;
        for(int x: nums) insert(x);
        int res = 0;
        for(int x: nums) res = Math.max(res, search(x));
        return res;
    }
}