《蓝桥杯每日一题》trie树·143. 最大异或对

用户10604450

发布于 2024-03-15 14:06:50

920

发布于 2024-03-15 14:06:50

文章被收录于专栏：练习两年半

题目描述

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

输入格式

第一行输入一个整数 N。

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

输出格式

输出一个整数表示答案。

数据范围

1≤N≤105,

0≤Ai<231

输入样例：

3 1 2 3

输出样例：

3

2.思路分析

从数组里挑两个数这两个数要满足异或结果最大

暴力枚举O(n2)O(n2) 一次枚举这两个数取异或最大值

Trie树优化 O(n∗31)O(n∗31)

对于某个数A 能与它异或得到较大结果的另一个数记为B

那么当A、B 越高位的数字不同时异或结果也就越大

什么意思呢举个例子

A = 1010, B = 1111 AB二进制表示中最高的不同位在右起第三位此时异或结果为A^B=0101

A = 1010, B = 0011 AB二进制表示中最高的不同位在右起第四位此时异或结果为A^B=1001

显然这时候B=0011才是我们需要的

如果有另一个B 使得不同位也在右起第四位呢那就看下一个不同位谁比较高

A=1010, B=0111 观察到第二高的不同位在右起第三位，异或结果为 A^B=1101

而B=0011第二高的不同位在右起第二位，异或结果为 A^B=1001

显然这时候就要选新的B了 B=0111

上面只是原理代码怎么实现呢这里要靠Trie树

每次选一个数A 然后从已经记录的数字里找能与它组成最大异或和的另一个数B

1. 按照A的二进制表示数从高到低依次遍历

2. 每次在树中找该位置的表示数的不同的数（不知道取什么名了如果A的某位是1就找0 是0就找1）

3. 如果树中恰好有记录到“在本位置不同的数” 那就移到对应的子树继续判断下一个位置

4. 但如果树中没有记录到“在本位置不同的数” （即所有数在这个位置都跟A一样）那就只好被迫移到对应的那棵子树上了

5. 遍历到第0位（也就是叶子节点）就能找到我们所需要的数B了

记异或和位res 初始时 res = 0

当某个位置有不同的数时这个位置异或完的结果必定为 1 所以res = (res << 1) + 1

如果没有不同的数只好选择相同的那这个位置异或完的结果必定为 0 所以res = (res << 1) + 0

直到遍历完叶子节点 res就是A能取得的最大异或和

3.Ac代码

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

    static int M=31,N=31*100010,idx=0;
    static int[][] trie=new int[N][2];
    public static void main(String[] args) throws IOException {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        int n=Integer.parseInt(br.readLine());
        String []s=br.readLine().split(" ");
        for (int i = 1; i <=n; i++) {
            insert(Integer.parseInt(s[i-1]));
        }
        int ans=-1;
        for (int i = 1; i <=n; i++) {
            int t=Integer.parseInt(s[i-1]);
            ans=Math.max(ans,query(t));
        }
        System.out.println(ans);

    }

    private static int query(int x) {
        int t=0,res=0;
        for(int i=M-1;i>=0;i--){
            int k=((x>>i)&1)^1;   //因为要找的是相反的数，所以异或一下
            if(trie[t][k]!=0){   //如果存过相反的，那么更新一下res并到下一节点
                t=trie[t][k];
                res=(res << 1) + 1;
            }else {
                t=trie[t][k^1];
                res<<=1;
            }
        }
        return res;
    }

    private static void insert(int x) {
        int t=0;
        for(int i=M-1;i>=0;i--){
            int k=(x>>i) &1;   // 取得第i位上的数  （这里i从右往左 从0开始）
            //如果没有创建过，那么先存进去
            if(trie[t][k]==0)  trie[t][k]=++idx;
            t=trie[t][k];  // 移到下一节点
        }
    }

}