Sword finger offer II 067. maximum XOR (medium prefix tree bit operation array)

The finger of the sword Offer II 067. Largest exclusive or

Given an array of integers nums , return nums[i] XOR nums[j] The largest operation result of , among 0 ≤ i ≤ j < n .

Example 1：

Input ：nums = [3,10,5,25,2,8]
Output ：28
explain ： The maximum result is 5 XOR 25 = 28.
Example 2：

Input ：nums = [0]
Output ：0
Example 3：

Input ：nums = [2,4]
Output ：6
Example 4：

Input ：nums = [8,10,2]
Output ：10
Example 5：

Input ：nums = [14,70,53,83,49,91,36,80,92,51,66,70]
Output ：127

Tips ：

1 <= nums.length <= 2 * 104
0 <= nums[i] <= 231 - 1

Advanced ： You can O(n) Is it time to solve this problem ？

source ： Power button （LeetCode）
link ：https://leetcode-cn.com/problems/ms70jA
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

analysis

Using prefix tree to realize O(n) Time complexity of , There are at most two nodes in each layer of the prefix tree 0 and 1, The first traversal will be the 32 Bits exist in the prefix tree , In the second traversal, XOR judgment is performed on each number and prefix tree to obtain the maximum XOR value .

Answer key （Java）

class Solution {
    
    static class TrieNode {
    
        TrieNode[] children;

        public TrieNode() {
    
            children = new TrieNode[2];
        }
    }

    public int findMaximumXOR(int[] nums) {
    
        TrieNode root = buildTrie(nums);
        int ans = 0;
        for (int num : nums) {
    
            TrieNode node = root;
            int xor = 0;
            for (int i = 31; i >= 0; i--) {
    
                int bit = (num >> i) & 1;
                if (node.children[1 - bit] != null) {
    
                    xor = (xor << 1) + 1;
                    node = node.children[1 - bit];
                } else {
    
                    xor = xor << 1;
                    node = node.children[bit];
                }
            }
            ans = Math.max(xor, ans);
        }
        return ans;
    }

    private TrieNode buildTrie(int[] nums) {
    
        TrieNode root = new TrieNode();
        for (int num : nums) {
    
            TrieNode node = root;
            for (int i = 31; i >= 0; i--) {
    
                int bit = (num >> i) & 1;
                if (node.children[bit] == null) {
    
                    node.children[bit] = new TrieNode();
                }
                node = node.children[bit];
            }
        }
        return root;
    }
}