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

该题同剑指 Offer II 067. 最大的异或

Approach 1

class Solution {
    public int findMaximumXOR(int[] nums) {
        int n = nums.length;
        Trie t = new Trie();
        int max = 0;
        for (int i = 0; i < n; i++) {
            t.insert(nums[i]);
            max = Math.max(max, t.search(nums[i]) ^ nums[i]);
        }
        return max;
    }

    class Trie {
        Trie[] next = new Trie[2];
        int val = -1;

        public void insert(int num) {
            int index = 31;
            int cur = num >> index;
            Trie t = this;
            while (index >= 0) {
                if (t.next[cur] == null) {
                    t.next[cur] = new Trie();
                }
                index--;
                t = t.next[cur];
                cur = (num >> index) & 1;
            }
            t.val = num;
        }

        public int search(int num) {
            Trie t = this;
            int index = 31;
            int cur = num >> index;
            int find = cur ^ 1;
            int res = 0;
            while (index >= 0) {
                if (t.next[find] != null) {
                    t = t.next[find];
                } else if (t.next[cur] != null) {
                    t = t.next[cur];
                }
                index--;
                cur = (num >> index) & 1;
                find = cur ^ 1;
            }
            res = t.val;
            return res;
        }
    }
}