LeetCode Maximum XOR of Two Numbers in an Array Given a non-empty array of numbers, a₀, a₁, a₂, … , a_n-1, where 0 ≤ a_i < 2³¹. Find the maximum result of a_i XOR a_j, 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.

---

给定一个非空数组，从中任意选两个数进行异或操作，问最大的异或结果是多少。 暴力两层循环肯定是不行的，本题需要一些位运算的技巧，解法参考讨论区。 题目限制数值范围在[0,2³¹)，所以异或操作最多需要考虑32位。我们从最高位开始考察，判断每一位在数组中异或之后能否得到1的结果。 假设我们已经知道前i-1位的异或最大值为ans，现在要求前i位的异或最大值。我们先把数组中所有数的前i位结果取出来，放到unordered_set<int> hash中。理想情况下，我们希望第i位的异或结果是1，即假设前i位的异或最大值为tmpmax=ans|(1<<i)。我们需要判断hash中是否有两个数异或能得到tmpmax的结果，如果能，说明前i位的异或最大值确实可以达到tmpmax。 也就是说我们需要从hash中选两个数a和b，判断a^b==tmpmax是否成立。常规方法是对hash两层循环判断，但是这样太慢了。利用异或的性质，我们有：如果a^b==tmpmax，则a=b^tmpmax和b=a^tmpmax。比如下面的例子，只是把^和=换了个位置，结果照样成立。

• 0^0=0 | 0=0^0
• 0^1=1 | 0=1^1
• 1^0=1 | 1=0^1
• 1^1=0 | 1=1^0

所以，我们只需要遍历hash中的数a，和tmpmax异或，如果异或结果b还在hash中，则说明b==a^tmpmax也在hash中，即a^b==tmpmax也成立。说明前i位的异或最大值确实可以达到tmpmax。 代码如下： [cpp] class Solution { public: int findMaximumXOR(vector<int>& nums) { int ans = 0, mask = 0; for (int i = 31; i >= 0; –i) { mask |= (1 << i); unordered_set<int> hash; for (const auto& num : nums) { hash.insert(num & mask); } int tmpmax = ans | (1 << i); for (const auto& prefix : hash) { if (hash.find(prefix ^ tmpmax) != hash.end()) { ans = tmpmax; break; } } } return ans; } }; [/cpp] 本代码提交AC，用时242MS。]]>