acwing 143.最大异或对(字典树)

发布时间:2024年01月19日

题目传送门:?143. 最大异或对

在给定的?N?个整数?A1,A2……AN?中选出两个进行?xor(异或)运算,得到的结果最大是多少?

输入格式

第一行输入一个整数?N。

第二行输入?N?个整数?A1~AN。

输出格式

输出一个整数表示答案。

数据范围

1≤N≤1e5,
0≤Ai<2^31

输入样例:
3
1 2 3
输出样例:
3
?试题解析

字典树存储+查询,

思路:将每个数以二进制的方式存入字典树
? ? ? ? ? ?查找的时候从最高位找与当前数据当前位数不同的位
? ? ? ? ? ?若没有不同的位,则选取相同的位,并继续下一位的选取

?代码如下:
#include<iostream>
using namespace std;
const int N = 100010, M = 31 * N;
// M代表一个数字串二进制可以到多长
int arr[N], son[M][2];
int idx;
void insert(int x) {
	int p = 0; //类似指针,指向当前节点
	for (int i = 30; i >= 0; i --) {
		int u = x >> i & 1;// 取x的最高位二进制数
		if (!son[p][u]) son[p][u] = ++idx; //若该节点不存在,创建节点,值为下一个位置
		p = son[p][u];//使p指向下一个节点
	}
}
int query(int x) {
	int p = 0, res = 0;
	for (int i = 30; i >= 0; i --) {
		int u = x >> i & 1;
		if (son[p][!u]) { //如果当前层有对应的不相同的数
			p = son[p][!u];
			res = res * 2 + !u;
		} else {
			p = son[p][u];
			res = res * 2 + u;
		}
	}
	return res;
}
int main() {
	int n;
	scanf("%d", &n);
	for (int i = 0; i < n; i ++) {
		scanf("%d", &arr[i]);
	}
	int res = 0;
	for (int i = 0; i < n; i ++) {
		insert(arr[i]);
		int t = query(arr[i]);
		res = max(res, t ^ arr[i]);
	}
	cout << res << endl;
	return 0;
}

文章来源:https://blog.csdn.net/m0_73612497/article/details/135685694
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。