421. 数组中两个数的最大异或值

给定一个非空数组，数组中元素为 a0, a1, a2, … , an-1，其中 0 ≤ ai < 231 。

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

你能在O(n)的时间解决这个问题吗？

示例:

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

输出: 28

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

PS：

前缀树

class Solution {

    class TrieNode {

        TrieNode zero;

        TrieNode one;

        int val;

        TrieNode() {

        }

    }

    class Trie {

        TrieNode root;

        Trie() {

            root = new TrieNode();

        }

        void insert(int num) {

            TrieNode node = root;

            for (int i = 31; i >= 0; i--) {

                int bit = num & (1 << i);

                if (bit == 0) {

                    if (node.zero == null) {

                        node.zero = new TrieNode();

                    }

                    node = node.zero;

                } else {

                    if (node.one == null) {

                        node.one = new TrieNode();

                    }

                    node = node.one;

                }

            }

            node.val = num;

        }

        int find(int num) {

            TrieNode node = root;

            for (int i = 31; i >= 0; i--) {

                int bit = num & (1 << i);

                if (bit == 0) {

                    node = node.one == null ? node.zero : node.one;

                } else {

                    node = node.zero == null ? node.one : node.zero;

                }

            }

            return node.val;

        }

    }

    // 数组中两个数的最大异或值

    public int findMaximumXOR(int[] nums) {

        Trie trie = new Trie();

        for (int num : nums) {

            trie.insert(num);

        }

        int res = 0;

        for (int num : nums) {

            int other = trie.find(num);

            res = Math.max(res, num ^ other);

        }

        return res;

    }

}