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

## [1707] 与数组中元素的最大异或值

[力扣原题链接](https://leetcode-cn.com/problems/maximum-xor-with-an-element-from-array/)

给你一个由非负整数组成的数组 `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：**

<pre>输入：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.
</pre>

**示例 2：**

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

**提示：**

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

### 我的思路

这种解法只能通过59的案例，第60个案例超时间了。

根据异或性质中，两个数异或的值不会超过两个数相加的值，可以先排序数组，通过二分查找找到第一个大于该数的值，从该值往下找，直到两数之和低于目前最大的异或值中止。

力扣题解使用二进制懒得看。
[力扣题解链接](https://leetcode-cn.com/problems/maximum-xor-with-an-element-from-array/solution/yu-shu-zu-zhong-yuan-su-de-zui-da-yi-huo-7erc/)

### 我的代码

```cpp
class Solution {
public:
 //二分查找找到第一个大于num的值
 int findHelper(vector<int> &nums,int num)
 {
 int left = 0;
 int right = (int)nums.size() - 1;
 while(left < right)
 {
 int tmp = (right - left) / 2 + left;
 if(nums[tmp] >= num)
 {
 right = tmp;
 }
 else
 {
 left = tmp + 1;
 }
 }
 return left;
 }

vector<int> maximizeXor(vector<int>& nums, vector<vector<int>>& queries) {
 //std::sort(nums.begin(),nums.end());
 set<int>s(nums.begin(), nums.end());
 nums.assign(s.begin(), s.end()); //利用set排序并去重，减少时间复杂度

int size = (int)queries.size();

vector<int> resurt(size,-1);
 for(int i = 0; i < size; ++i)
 {
 int max_num = -1;
 int find_indxe = findHelper(nums,queries[i][1]);
 for(int j = find_indxe; j >= 0; --j)
 {
 if(nums[j] > queries[i][1]) continue; //不符合的数值
 if(nums[j] + queries[i][0] <= max_num) break; //两数之和无法大于目前最大异或值 中止

max_num = std::max(nums[j] ^ queries[i][0],max_num);
            }
            resurt[i] = max_num;
        }

return resurt;
    }
};
```

### 力扣题解

```cpp
class Trie {
public:
    const int L = 30;

Trie* children[2] = {};
    int min = INT_MAX;

void insert(int val) {
        Trie* node = this;
        node->min = std::min(node->min, val);
        for (int i = L - 1; i >= 0; --i) {
            int bit = (val >> i) & 1;
            if (node->children[bit] == nullptr) {
                node->children[bit] = new Trie();
            }
            node = node->children[bit];
            node->min = std::min(node->min, val);
        }
    }

int getMaxXorWithLimit(int val, int limit) {
 Trie* node = this;
 if (node->min > limit) {
 return -1;
 }
 int ans = 0;
 for (int i = L - 1; i >= 0; --i) {
 int bit = (val >> i) & 1;
 if (node->children[bit ^ 1] != nullptr && node->children[bit ^ 1]->min <= limit) {
 ans |= 1 << i;
 bit ^= 1;
 }
 node = node->children[bit];
 }
 return ans;
 }
};

class Solution {
public:
 vector<int> maximizeXor(vector<int> &nums, vector<vector<int>> &queries) {
 Trie* t = new Trie();
 for (int val : nums) {
 t->insert(val);
 }
 int numQ = queries.size();
 vector<int> ans(numQ);
 for (int i = 0; i < numQ; ++i) {
 ans[i] = t->getMaxXorWithLimit(queries[i][0], queries[i][1]);
 }
 return ans;
 }
};
```