Leetcode 1707 与数组中元素的最大异或值

1707. 与数组中元素的最大异或值
难度
困难

给你一个由非负整数组成的数组 nums 。另有一个查询数组 queries ，其中 queries[i] = [xi, mi] 。

第 i 个查询的答案是 xi 和任何 nums 数组中不超过 mi 的元素按位异或（XOR）得到的最大值。换句话说，答案是 max(nums[j] XOR xi) ，其中所有 j 均满足 nums[j] <= mi 。如果 nums 中的所有元素都大于 mi，最终答案就是 -1 。

返回一个整数数组 answer 作为查询的答案，其中 answer.length == queries.length 且 answer[i] 是第 i 个查询的答案。

示例 1：

输入：nums = [0,1,2,3,4], queries = [[3,1],[1,3],[5,6]]
输出：[3,3,7]
解释：
1) 0 和 1 是仅有的两个不超过 1 的整数。0 XOR 3 = 3 而 1 XOR 3 = 2 。二者中的更大值是 3 。
2) 1 XOR 2 = 3.
3) 5 XOR 2 = 7.
示例 2：

输入：nums = [5,2,4,6,6,3], queries = [[12,4],[8,1],[6,3]]
输出：[15,-1,5]
 

提示：

1 <= nums.length, queries.length <= 105
queries[i].length == 2
0 <= nums[j], xi, mi <= 109

 提示在做此题之前强烈建议先去做Leetcode 421 数组中两个数的最大异或值

思路:

1.首先解决 Leetcode 421数组中两个数的最大异或值

关于异或运算的特点我们知道异或运算 异或位相同则为0，不同则为1 同时异或被称为不进位加法

也就是说进行异或操作时从高位到低位我们尽量选择当前操作位不同的两个数组中的数

进行异或操作 

我们借助字典树实现

将数组中的数字的二进制字符串依次取出构造字典树

我们知道当前位只有两个选择 0或者1 所以字典树的每个节点保存一个指针数组

Node* next[2]={nullptr};

如果存在该位的下一位为0 那么next[0]=new Node() 1同理

我们将每个int类型的数通过移位操作将其二进制字符串作为前缀构造字典树（也称前缀树）

遍历数组,当前检索的元素为Xi,那么我们通过移位操作取出其对应的位数，结合异或操作的 特性

每次尽量沿着和当前位数相反的路径走下去以获取异或运算的最大值，每次更新扫描完当前检索元素后得到的最大异或值，检索完全部元素后得到数组任意两个元素异或的最大值

2.此题要求我们得到Xi与数组中所有不超过Mi的值异或得到的最大值

一个可行的思路是在进行异或操作时，字典树中只有比mi小的元素，所以我们首先将原数组nums排序

然后将queries按照mi的大小排序并且由于返回要求需要记录排序之前的位置

按顺序处理queries数组，由于其按照mi大小排序，我们在进行异或操作前为了保证比mi小的元素都在字典树中，只需要维护一个在nums上向右移动的指针。

之后的操作同上，最后根据索引找到结果应该存放的位置

Trips：

其中记录queries元素在排序前的位置的一个容易想到的方法是map 但笔者用map会出现两个vector<int>对应相同的哈希值导致某个queries元素的结果没有正确存放到结果容器的正确位置

此题中一个可行的方法是将排序前得位置直接存到queries元素中，因为其本身就是个vector<int>

具体代码如下

struct Node {
    Node* next[2] = { nullptr };
};
bool cmp(vector<int>&a,vector<int>&b){
    return a[1]<b[1];
}
class Solution {
public:
    void Insert(int num, Node* root) {
        for (int i = 30; i >= 0; i--) {
            int t = (num >> i & 1);
            if (!root->next[t]) {
                root->next[t] = new Node();
            }
            root=root->next[t];
        }
    }
    vector<int> maximizeXor(vector<int>& nums, vector<vector<int>>& queries) {
        vector<int> answer(queries.size(),0);
        sort(nums.begin(),nums.end());//对xi数组排序
        for(int i=0;i<queries.size();i++){
           queries[i].push_back(i);
        }
        sort(queries.begin(),queries.end(),cmp);
        int p=0;Node * root=new Node();
        Node* temp=root;int res=0;
        for( auto& q:queries){
            temp=root;res=0;
            while(nums[p]<=q[1]&&p<nums.size()) Insert(nums[p++],root);
            if(p!=0) { //没有比mi小的元素 
            for(int i=30;i>=0;i--){
                int t=(q[0]>>i&1);
                if(temp->next[!t]){
                    temp=temp->next[!t];
                    res+=(1<<i);
                }
                else temp=temp->next[t];
            }
            }
            else res=-1;
            answer[q[2]]=res;
        }
        return answer;
    }
};

字典树代码

struct Node {
    Node* next[2] = { nullptr };
};

void Insert(int num, Node* root) {
        for (int i = 30; i >= 0; i--) {
            int t = (num >> i & 1);
            if (!root->next[t]) {
                root->next[t] = new Node();
            }
            root=root->next[t];
        }
    }