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.
这道题是一道典型的位操作Bit Manipulation的题目，我开始以为异或值最大的两个数一定包括数组的最大值，但是OJ给了另一个例子{10,23,20,18,28}，这个数组的异或最大值是10和20异或，得到30。那么只能另辟蹊径，正确的做法是按位遍历，题目中给定了数字的返回不会超过231,那么最多只能有32位，我们用一个从左往右的mask，用来提取数字的前缀，然后将其都存入set中，我们用一个变量t，用来验证当前位为1再或上之前结果res，看结果和set中的前缀异或之后在不在set中，这里用到了一个性质，若a^b=c，那么a=b^c，因为t是我们要验证的当前最大值，所以我们遍历set中的数时，和t异或后的结果仍在set中，说明两个前缀可以异或出t的值，所以我们更新res为t，继续遍历，如果上述讲解不容易理解，那么建议自己带个例子一步一步试试，并把每次循环中set中所有的数字都打印出来，基本应该就能理解了，参见代码如下：
class Solution { public: int findMaximumXOR(vector<int>& nums) { int res = 0, mask = 0; for (int i = 31; i >= 0; --i) { mask |= (1 << i); set<int> s; for (int num : nums) { s.insert(num & mask); } int t = res | (1 << i); for (int prefix : s) { if (s.count(t ^ prefix)) { res = t; break; } } } return res; } };解法二：
遍历数组，对每个数的二进制构建一棵字典树。
再次遍历数组，对每个数的每个二进制位与1异或：数组元素的二进制位为0，则寻找到值为1的子树，数组元素的二进制位为1，则寻找到值为0的子树。(当然也可以与0异或)
与1异或后子树不为空，则可计数并累加；与1异或后子树为空，则继续向下查找。
划重点！！！
对数组元素的二进制构建Trie树。寻找子树的时候，与1(或0)异或。 class Solution { public: //定义数的节点类型 struct Trie { vector<Trie*> child; Trie() : child(vector<Trie*>(2, NULL)) {} }; //建树 void add(int num) { Trie* tmp = root; for(int i = 31; i >= 0; i--) { int val = (num >> i) & 1; if(!tmp->child[val]) { tmp->child[val] = new Trie(); //有节点即表示有数，null表示没有数 } tmp = tmp->child[val]; } } //查找数 int search(int num) { int ans = 0; Trie* tmp = root; for(int i = 31; i >= 0; --i) { int val = (num >> i) & 1; ans = ans << 1; if(tmp->child[val]) { ans++; tmp = tmp->child[val]; } else { tmp = tmp->child[!val]; //不可能到不了根节点，非此即彼，所以此时选择child[!val]一定存在 } } return ans; } int findMaximumXOR(vector<int>& nums) { root = new Trie(); for(auto val : nums) { add(val); } int ans = INT_MIN; for(auto val : nums) { ans = max(ans, search(~val)); //取反保证查找返回的是“异或”后的最大值 } return ans; } private: Trie* root; };总结：
两种方法思路完全不同，第一种利用异或的性质，a^b=c，则a=b^c，类似于预设未知数c，通过判断b^c是否有对应的a来判断c的值，若有c=1，若无c=0；第二种方法则将问题转换为二叉树的查找问题，将找数变为找叶子结点，十分巧妙。
