标题文字

链接：

可以用trie tree来做。把所有num放进tree，之后对每一个num从最高位找是否存在和当前bit不同的path。把build tree单独写一个函数，结果TLE了，所以放一起了。。

public class Solution {    public int findMaximumXOR(int[] nums) {        /* trie tree: root is the largest bit         * 32 bits         */        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];            }        }                int globalMax = Integer.MIN_VALUE;                for(int num : nums) {            int local = 0;            TrieNode node = root;            for(int i = 31; i >= 0; i--) {                int bit = (num >> i) & 1;                if(node.children[bit ^ 1] != null) {                    local += (1 << i);                    node = node.children[bit ^ 1];                }                else node = node.children[bit];            }            globalMax = Math.max(globalMax, local);        }        return globalMax;    }        class TrieNode {        TrieNode[] children = new TrieNode[2];    }    }

看到discussion还有一种简单的方法，从最高位开始扫，每次在nums里面找有没有两个数XOR可以等于1。如果有就把1放进去，当前结果累计到下一个循环。用一个set存到第i位位置的数，然后通过XOR就能找到有没有可以匹配的数。

1. 把所有num(31, i)放进set里面

2. 找出set中是否有两个数XOR后等于i = 1的结果

3. 有就更新globalMax

第二步根据 x ^ y = z, then x ^ z = y

public class Solution {    public int findMaximumXOR(int[] nums) {         int globalMax = 0, highestBits = 0;         for(int i = 31; i >= 0; i--) {             // 1000 -> 1100 -> 1110 -> 1111             highestBits = highestBits | (1 << i);             Set
    
      set = new HashSet();             for(int num : nums) {                 set.add(num & highestBits);             }                          // find if current bit can be 1             int addOne = globalMax | (1 << i);             for(int num : set) {                 if(set.contains(num ^ addOne)) {                     globalMax = addOne;                     break;                 }             }         }         return globalMax;    }}