421. Maximum XOR of Two Numbers in an Array

class Solution {
    private static class TrieNode {
        private int num;
        private final TrieNode[] children = new TrieNode[2];
    }

    private static class Trie {
        private final TrieNode root = new TrieNode();

        public void insert(int num) {
            TrieNode node = root;
            // 从高位到低位依次插入，题目保证了无负数，所以跳过了符号位
            for (int offset = 30; offset >= 0; offset--) {
                int index = (num >> offset) & 1;
                if (node.children[index] == null) {
                    node.children[index] = new TrieNode();
                }
                node = node.children[index];
            }

            node.num = num;
        }

        public int getAnotherNum(int num) {
            TrieNode node = root;
            for (int offset = 30; offset >= 0; offset--) {
                int index = 1 - ((num >> offset) & 1);
                if (node.children[index] == null) {
                    node = node.children[1 - index];
                } else {
                    node = node.children[index];
                }
            }

            return node.num;
        }
    }

    public int findMaximumXOR(int[] nums) {
        int maxXor = 0;

        Trie trie = new Trie();
        for (int num : nums) {
            trie.insert(num);
            int anotherNum = trie.getAnotherNum(num);
            maxXor = Math.max(maxXor, num ^ anotherNum);
        }

        return maxXor;
    }
}

注意该题是计算两个数的最大异或数值，而不是最大的不同比特个数，所以我们从高位贪心找不同的比特即可。

References

421. Maximum XOR of Two Numbers in an Array
LCR 067. 数组中两个数的最大异或值