421. Maximum XOR of Two Numbers in an Array.md

421. Maximum XOR of Two Numbers in an Array

https://leetcode.com/problems/maximum-xor-of-two-numbers-in-an-array/

Given a non-empty array of numbers, a0, a1, a2, … , an-1, where 0 ≤ ai < 231.

Find the maximum result of ai XOR aj, where 0 ≤ i, j < n.

Could you do this in O(n) runtime?

Example:

Input: [3, 10, 5, 25, 2, 8]

Output: 28

Explanation: The maximum result is 5 ^ 25 = 28.

思路

• Trie, 具体实现如下：

简单来说，就是先找到最高位的1，然后如何选择呢？因为对于异或来说，要想最终结果最大，那么尽可能要找两个数，使他们每一个 bit 之间都互不相同，这样他们异或的结果中的“1”越多，自然结果就越大。那么如何找到“尽可能每位不同”的数字呢？很简单，因为我们已经构建好了 trie，先找到最高位1的那个分支，例如图中的第一层右半边有1，那么我们就以这个分支为基准，找“与其相反”的 bit 是否在同一层，以此类推。找得到相反的bit，就选它，找不到，就保持不变，继续往下遍历。

代码

class TrieNode {
  HashMap<Character, TrieNode> children = new HashMap<Character, TrieNode>();
  public TrieNode() {      
  }
}

class Solution {
    public int findMaximumXOR(int[] nums) {
        int L = nums[0];
        for (int num: nums) L = Math.max(L, num);
        // here N means the longest length of number digit.
        L = (Integer.toBinaryString(L)).length();
        
        // zero padding
        int n = nums.length, bitmask = 1<<L;
        String[] strNums = new String[n];
        for (int i = 0; i < n; i++) {
            strNums[i] = Integer.toBinaryString(bitmask | nums[i]);
        }
        
        // construct the trie
        TrieNode trie = new TrieNode();
        int max_ = 0;
        for (String num: strNums) {
            TrieNode node = trie, xorNode = trie;
            int cur_ = 0;
            for (Character bit : num.toCharArray()) {
                // insert new num in trie
                if (node.children.containsKey(bit)) {
                    // different number may have the same "0" or "1" in the same position,
                    // like "00101" and "11101" -> "101" is same
                    node = node.children.get(bit);
                }
                else {
                    TrieNode newNode = new TrieNode();
                    node.children.put(bit, newNode);
                    node = newNode;
                }
                
                
                // compute the maxXOR
                // using selection policy
                Character oppo = bit == '1' ? '0' : '1';
                if (xorNode.children.containsKey(oppo)) {
                    cur_ = (cur_ << 1) | 1;
                    xorNode = xorNode.children.get(oppo);
                }
                else {
                    cur_ = cur_ << 1;
                    xorNode = xorNode.children.get(bit);
                }
            }
            max_ = Math.max(max_, cur_);
        }
        return max_;
    }
}