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

输入格式

第一行输入一个整数N。

SRE实战 互联网时代守护先锋,助力企业售后服务体系运筹帷幄!一键直达领取阿里云限量特价优惠。

第二行输入N个整数A1A1~ANAN。

输出格式

输出一个整数表示答案。

数据范围

1N1051≤N≤105,
0Ai<2310≤Ai<231

输入样例:

3
1 2 3

输出样例:

3


暴力做法:O(n^2)
import java.util.Scanner;

public class Main{
          static int a[]=new int[100005];
          public static void main(String[] args) {
                Scanner scan=new Scanner(System.in);
                int n=scan.nextInt();
                for(int i=0;i<n;i++) a[i]=scan.nextInt();
                int max=-1;
                  for(int i=0;i<n;i++)
                      for(int j=0;j<i;j++)
                          max=Math.max(max, a[i]^a[j]);
                  System.out.println(max);
                          
        }
}
对此步做优化
 for(int i=0;i<n;i++)
     for(int j=0;j<i;j++)//----这一步
        max=Math.max(max, a[i]^a[j]);

O(n*logn)

 143. 最大异或对(Trie树存整数+二进制) 算法

 

 异或运算,同为0,不同为1

 建立trie树,左0右1

 先插入一个整数,然后查询,查询过程中,如果u是1,就尽可能往0那边走;如果u是0,就尽可能往1那边走

AC代码:
import java.util.Scanner;

public class Main{
        static final int N=100005,M=N*31;
        static int a[]=new int[N];
        static int son[][]=new int [M][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,res=0;
                for(int i=30;i>=0;i--){
                        int u=x>>i&1;
                        //如果u是1,就尽可能往0那边走;如果u是0,就尽可能往1那边走
                        if(son[p][u==1?0:1]!=0){
                                p=son[p][u==1?0:1];
                                res=res*2+(u==1?0:1);//加括号,优先级问题
                        }
                        else{
                                p=son[p][u];
                                res=res*2+u;
                        }
                }
                return res;
        }
        public static void main(String[] args) {
                 Scanner scan=new Scanner(System.in);
                 int n=scan.nextInt();
                 for(int i=0;i<n;i++) a[i]=scan.nextInt();
                 int res=0;
                 for(int i=0;i<n;i++){
                         insert(a[i]);
                         int num=query(a[i]);
                         res=Math.max(res, a[i]^num);
                 }
                 System.out.println(res);
        }
}

 

扫码关注我们
微信号:SRE实战
拒绝背锅 运筹帷幄