- 数组中两个数的最大异或值
给你一个整数数组 nums ，返回 nums[i] XOR nums[j] 的最大运算结果，其中 0 ≤ i ≤ j < n 。
进阶：你可以在 O(n) 的时间解决这个问题吗？
示例 1：
输入：nums = [3,10,5,25,2,8]
输出：28
解释：最大运算结果是 5 XOR 25 = 28.
示例 2：
输入：nums = [0]
输出：0
示例 3：
输入：nums = [2,4]
输出：6
示例 4：
输入：nums = [8,10,2]
输出：10
示例 5：
输入：nums = [14,70,53,83,49,91,36,80,92,51,66,70]
输出：127
提示：
1 <= nums.length <= 2 * 104
0 <= nums[i] <= 231 - 1
题解
很巧妙的题目，我们固定死把每个数字都转换成长度为31的二进制数，记得用long long表示运算，然后我们就从31位不断从高位向低位类似前缀编码的操作，判断下能否构成答案，因为异或操作有个特点是：a ^ b = c, a ^ c = b。
所以同样需要把每个数字都进行前缀编码，用set储存优化查询效率，顺便去重。
AC代码
class Solution {
public:
typedef long long ll;
set<ll>number[31];
void fun(ll x)
{
vector<ll>res;
while(x>0)
{
res.push_back(x%2);
x/=2;
}
for(int i=res.size();i<31;i++)
res.push_back(0);
ll ans = 0;
for(int i=30;i>=0;i--)
{
ans *= 2;
ans += res[i];
number[i].insert(ans);
}
}
int findMaximumXOR(vector<int>& nums)
{
for(int i=0;i<nums.size();i++)
fun(nums[i]);
ll ans = 0,answer=0;
set<ll>::iterator it;
for(int i=30;i>=0;i--)
{
ans = answer * 2 + 1;
bool flag = false;
for(it=number[i].begin();it!=number[i].end();it++)
{
int res = (*it) ^ ans;
if(number[i].find(res)!=number[i].end())
{
flag = true;
break;
}
}
if(flag)
answer = answer * 2 + 1;
else
answer = answer * 2 + 0;
}
return answer;
}
};
