题目描述
样例
import java.io.BufferedOutputStream;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
public class Main {
static final int N = 3100010;
static int son[][] = new int[N][2];
static int idx = 0;
//插入子节点
static void insert(int x)
{
int p = 0;
for(int i=30;i>=0;i--)
{
int u = x>>i&1;
if(son[p][u]==0) son[p][u]=++idx;
p=son[p][u];
}
}
//查询
static int query(int x)
{
int p=0;
int res=0;
for(int i=30;i>=0;i--)
{
int u = x>>i&1;//这个是判断x的每一位是不是1
if(son[p][1-u]!=0)//如果该节点的u是0,则判断一下这一层有没有相反的0-1,1-0
{
res+=(1<<i);//如果有,res就顺位从高到低加上这个异或数
p=son[p][1-u];//并且p到达最优解的节点
}else
{
p=son[p][u];//否则p就往最坏解走
}
}
return res;
}
public static void main(String args[]) throws IOException
{
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
int n = Integer.parseInt(in.readLine());
int res = 0;
String s[]= in.readLine().split(" ");
for(int i=0;i<n;i++)
{
insert(Integer.parseInt(s[i]));
}
for(int i=0;i<n;i++)
{
res=Math.max(res, query(Integer.parseInt(s[i])));
}
out.print(res);
out.flush();
out.close();
in.close();
}
}
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla