leetcode 421. Maximum XOR of Two Numbers in an Array | 421. 数组中两个数的最大异或值（位运算，Trie前缀树）

雨点打透心脏的1/2处 2022-09-03 03:26 120阅读 0赞

## 题目 ##

[https://leetcode.com/problems/maximum-xor-of-two-numbers-in-an-array/][https_leetcode.com_problems_maximum-xor-of-two-numbers-in-an-array]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]

## 题解 ##

自己没有思路，看了答案之后自己写的。

参考：[Python3 巧妙利用前缀树剪枝，复杂度 O(N)][Python3 _ O_N]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70 1]

class Trie { 
        Trie[] children;
        public Trie() { 
            children = new Trie[2];
        }
    }
    
    class Solution { 
        public int findMaximumXOR(int[] nums) { 
            Trie root = new Trie();
            int max = Integer.MIN_VALUE;
            for (int n : nums) { 
                int curMax = 0;
                Trie buildNode = root; // node for build Trie
                Trie xorNode = root; // node for calculate XOR
    
                for (int j = 31; j >= 0; j--) { 
                    int b = 1 & (n >>> j);
                    // 构造Trie
                    if (buildNode.children[b] == null)
                        buildNode.children[b] = new Trie();
                    buildNode = buildNode.children[b];
                    // 选择XOR的操作数
                    curMax = curMax << 1;
                    if (xorNode.children[1 - b] != null) {  // 有相异的位
                        curMax += 1;
                        xorNode = xorNode.children[1 - b];
                    } else {  // else不会是null，因为任何一个分支的高度均为32
                        curMax += 0;
                        xorNode = xorNode.children[b];
                    }
                }
                max = Math.max(curMax, max);
            }
            return max;
        }
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 2]

[https_leetcode.com_problems_maximum-xor-of-two-numbers-in-an-array]: https://leetcode.com/problems/maximum-xor-of-two-numbers-in-an-array/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]: /images/20220829/a126d3b524944e68ad4e6e4d4e040303.png
[Python3 _ O_N]: https://leetcode-cn.com/problems/maximum-xor-of-two-numbers-in-an-array/solution/python3-qiao-miao-li-yong-qian-zhui-shu-0alcy/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70]: /images/20220829/ee5482b0c078431483bccb8a7c5b7de4.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 1]: /images/20220829/ea89ed64f3d044ba893af36f409deb5b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70 1]: /images/20220829/f365b41179234bd5889cbf51cd155a4f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 2]: /images/20220829/7e4b08cd904c40d99a9535bbed41b945.png