Description:
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.
Link:
https://leetcode.com/problems/maximum-xor-of-two-numbers-in-an-array/description/
解题方法：
在解题之前，首先要了解2个事情：
- 两个数XOR的结果取决于这两位数的二进制形式每一位是否相同。当相同时，结果在这一位上为0；当不同时，结果在这一位上为1。
- 假设我们有3个数：a, b, c；当a 和 b以及b和c在第1位上有不同时（a和c相同），那么最大的XOR只会出现在aXORb与bXORc之间。
解题方法：
- 我们将数组里面的元素分组，以第一次出现不同的位置分为set0和set1两组，进入递归函数
（set0, set1, poi - 1）； - 将在set0和set1中的数根据下一位(poi)的值各自再分为两组set01和set00, set10和set11；
- 当set01和set10或者set00和set11同时存在时，意味着最大的XOR值在这一位上必定为1，在这层递归中
最大XOR值=1<<poi + max(下一层递归(set01, set10, poi - 1),下一层递归(set00, set11, poi - 1))；如果这两组都不存在，则将位置向右再移一位，重复进行操作2；
Time Complexity：
O(N)
完整代码：
class Solution
{
public:
int findMaximumXOR(vector<int>& nums)
{
int result = 0;
vector<int> set0;
vector<int> set1;
for(int poi = 31; poi >= 0; poi--)
{
set0.clear();
set1.clear();
for(int i: nums)
{
if(i & (1 << poi))
set1.push_back(i);
else
set0.push_back(i);
}
if(!set0.empty() && !set1.empty())
{
result += (1 << poi);
result += helper(set0, set1, poi - 1);
break;
}
}
return result;
}
int helper(vector<int>& set0, vector<int>& set1, int poi)
{
if(poi < 0)
return 0;
int result = 0;
vector<int> set00;
vector<int> set01;
vector<int> set10;
vector<int> set11;
for(int i : set0)
{
if(i & (1 << poi))
set01.push_back(i);
else
set00.push_back(i);
}
for(int i : set1)
{
if(i & (1 << poi))
set11.push_back(i);
else
set10.push_back(i);
}
int temp0 = 0, temp1 = 0;
if(!set00.empty() && !set11.empty())
{
temp0 = (1 << poi) + helper(set00, set11, poi - 1); //参数的顺序不能出错
}
if(!set01.empty() && !set10.empty())
{
temp1 =(1 << poi) + helper(set01, set10, poi - 1); //参数的顺序不能出错
}
if(temp0 || temp1)
{
return result += max(temp0, temp1);
}
else
return helper(set0, set1, poi - 1);
}
};
