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

给你一个整数数组 nums ，返回 nums[i] XOR nums[j] 的最大运算结果，其中 0 ≤ i ≤ j < n 。

进阶：你可以在 O(n) 的时间解决这个问题吗？

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/maximum-xor-of-two-numbers-in-an-array
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

哈希表

import java.util.HashSet;
import java.util.Set;

class Solution {
    // 最高位的二进制位编号为 30
    static final int HIGH_BIT = 30;

    public int findMaximumXOR(int[] nums) {
        int x = 0;
        for (int k = HIGH_BIT; k >= 0; --k) {
            Set seen = new HashSet();
            // 将所有的 pre^k(a_j) 放入哈希表中
            for (int num : nums) {
                // 如果只想保留从最高位开始到第 k 个二进制位为止的部分
                // 只需将其右移 k 位
                seen.add(num >> k);
            }

            // 目前 x 包含从最高位开始到第 k+1 个二进制位为止的部分
            // 我们将 x 的第 k 个二进制位置为 1，即为 x = x*2+1
            int xNext = x * 2 + 1;
            boolean found = false;

            // 枚举 i
            for (int num : nums) {
                if (seen.contains(xNext ^ (num >> k))) {
                    found = true;
                    break;
                }
            }

            if (found) {
                x = xNext;
            } else {
                // 如果没有找到满足等式的 a_i 和 a_j，那么 x 的第 k 个二进制位只能为 0
                // 即为 x = x*2
                x = xNext - 1;
            }
        }
        return x;
    }
}

字典树

class Solution {
    public int findMaximumXOR(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        Trie trie = new Trie();
        trie.insert(nums[0]);
        int ans = 0;
        for (int i = 1; i < nums.length; ++i) {
            ans = Math.max(ans, trie.search(nums[i]));
            trie.insert(nums[i]);
        }
        return ans;
    }
}

class Trie {

    private Node root = new Node();

    class Node {
        Node[] children = new Node[2];
    }

    public void insert(int num) {
        Node cur = root;
        for (int i = 31; i >= 0; --i) {
            int path = (num >> i) & 1;
            if (cur.children[path] == null) {
                cur.children[path] = new Node();
            }
            cur = cur.children[path];
        }
    }

    public int search(int num) {
        Node cur = root;
        int ans = 0;
        for (int i = 31; i >= 0; --i) {
            int path = (num >> i) & 1;
            int best = i == 31 ? path : path ^ 1;
            best = cur.children[best] == null ? best ^ 1 : best;
            ans = ans | ((best ^ path) << i);
            cur = cur.children[best];
        }
        return ans;
    }
}