数组中两个数的最大异或值(字典树+贪心)

本文主要是介绍数组中两个数的最大异或值(字典树+贪心)，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

传送门

题目描述:

给你一个整数数组 nums ，返回 nums[i] XOR nums[j] 的最大运算结果，其中 0 ≤ i ≤ j < n 。

进阶：你可以在 O(n) 的时间解决这个问题吗？

思路:直接进阶,看了题解才想出来....

字典树贪心,循环遍历每个数,对每个数的30位二进制位倒着建树,在插入该数之前我们首先对以及建好的树

进行贪心,查找当前数能与之前数异或出的最大值,具体如何选:

定义x表示能异或出的最大值,

如果当前位置为1,则看已经建成的树的当前位置是否能选0,能选0就选0,x+=(1<<i),

不能选0,就只能选1,x不变,因为两个1异或为0,

如果当前位置为0,则判断树中该位置是否能选1,能选就x=x+(1<<i),反之就选0,x不变

可以贪心的原因:因为我们是倒着判断每一位的,即从高位到低位,如果高位能取1,就一定

是最好的选择。

AC代码:

const int maxn=200005;
class Solution {
public:
    int tree[maxn][2],tot;
    void insert(int x){
    int now=0;
    for(int i=30;i>=0;i--){
        if(tree[now][(x&(1<<i))!=0]){
            now=tree[now][(x&(1<<i))!=0];
        }else{
            tree[now][(x&(1<<i))!=0]=++tot;
            now=tot;
        }
    }   
    }
    int get(int x){
        int now=0,ans=0;
        for(int i=30;i>=0;i--){//倒着贪心
            if((x&(1<<i))!=0){
                if(tree[now][0]){
                    ans+=(1<<i);
                    now=tree[now][0];
                }else {
                    now=tree[now][1];
                }
            }else{
                if(tree[now][1]){
                    ans+=(1<<i);
                    now=tree[now][1];
                }else {
                    now=tree[now][0];
                }
            }
        }
        return ans;
    }
    int findMaximumXOR(vector<int>& nums) {
    if(nums.size()==1)return 0;
    insert(nums[0]);//先插入第一个数
    int res=0;
    for(int i=1;i<nums.size();i++){
       res=max(get(nums[i]),res);//找出当前数和之前的数异或结果的最大值get(x);
       insert(nums[i]);
    }
    return res;
    }
};

这篇关于数组中两个数的最大异或值(字典树+贪心)的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！