题目描述
在给定的 N 个整数 A1,A2……AN 中选出两个进行 xor(异或)运算,得到的结果最大是多少?
输入格式
第一行输入一个整数 N。
第二行输入 N 个整数 A1~AN。
输出格式
输出一个整数表示答案。
数据范围
1≤N≤105,
0≤Ai<231
样例
输入样例
3
1 2 3
输出样例
3
算法1
(trie树) $O()$
时间复杂度
参考文献
python3 代码
n = int(input())
nums = [int(x) for x in input().split()]
class Trie:
def __init__(self):
self.child = [None for _ in range(2)]
def insert(self, x: int) -> None:
root = self
for i in range(30, -1, -1):
ID = (x >> i) & 1
if root.child[ID] == None:
root.child[ID] = Trie()
root = root.child[ID]
def query(self, x: int) -> int:
root = self
y = 0
for i in range(30, -1, -1):
ID = (x >> i) & 1
if root.child[(1-ID)] == None:
root = root.child[ID]
y = y * 2 + ID
else:
root = root.child[(1-ID)]
y = y * 2 + (1-ID)
return y ^ x
res = 0
root = Trie()
for x in nums:
root.insert(x)
res = max(res, root.query(x))
print(res)
C++ 代码
#include<bits/stdc++.h>
using namespace std;
class Trie
{
public:
Trie * child[2];
// vector<Trie *> child;
Trie()
{
memset(child, 0, sizeof(child));
// child.resize(2);
}
void insert(int x)
{
Trie * root = this;
for (int i = 30; i > -1; i --)
{
int ID = (x >> i) & 1;
if (root->child[ID] == NULL)
root->child[ID] = new Trie();
root = root->child[ID];
}
}
int query(int x)
{
Trie * root = this;
int y = 0;
for (int i = 30; i > -1 ; i --)
{
int ID = (x >> i) & 1;
if (root->child[!ID] != NULL)
{
root = root->child[!ID];
y = y * 2 + !ID;
}
else
{
root = root->child[ID];
y = y * 2 + ID;
}
}
return x ^ y;
}
};
int main()
{
int n;
cin >> n;
int nums[n];
memset(nums, 0, sizeof(nums));
for (int i = 0; i < n; i ++)
cin >> nums[i];
Trie * root = new Trie();
int res = 0;
for (int & x: nums)
{
root->insert(x);
res = max(res, root->query(x));
}
cout << res << endl;
return 0;
}