[LeetCode]Maximum XOR of Two Numbers in an Array

XOR的运算法则是相同变0，不同变1。那么这道题的思路就是，对于每一个数，从高位到低位寻找每一位尽量不相同的数，这样可以让这个数和其他数XOR的结果最大。然后我们从这些值中取出最大值，就是我们要求的值。如何在O(1)的时间内寻找每一位尽量不同的数呢？Trie是一个很好的数据结构可以帮助我们实现，关于Trie的介绍可以参考这一片文章。具体思路就是，如果能找到和当前位数不同的就去对应的分支，否则就去另外一个。因为只有0和1可以选，只要trie不为空，当前节点只要没有0/1的子节点，就必然有另一个对应的节点，所有的数的bit位数都是一样的。时间复杂度，空间复杂度O(n)，代码如下：


当然之前为了省事，尝试过直接用set来解决，具体的思路是一样的，先贴代码（这个代码是错误的）：


但是这段代码却无法得到我们想要的结果，原因注释中已经说明。因为set存有所有的前缀，但我们再retrieve的时候无法区分这个是长度为多少的前缀，如果长度为2的前缀被认为长度为3的前缀就会有问题。但是Trie就不存在这方面的问题。
当然并不是说用set就没法做，我们只需要每次处理长度为k的prefix，之后清空set接着处理长度为k + 1的prefix就可以了，时间复杂度O(n)，空间复杂度O(n)，代码如下：