传送门
题目描述:
给你一个整数数组 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; } };