题目描述
给定一个由非负整数组成的数组 nums
。另有一个查询数组 queries
,其中 queries[i] = [x_i, m_i]
。
第 i
个查询的答案是 x_i
和任何 nums
数组中不超过 m_i
的元素按位异或(XOR)得到的最大值。换句话说,答案是 max(nums[j] XOR x_i)
,其中所有 j
均满足 nums[j] <= m_i
。如果 nums
中的所有元素都大于 m_i
,最终答案就是 -1
。
返回一个整数数组 answer
作为查询的答案,其中 answer.length == queries.length
且 answer[i]
是第 i
个查询的答案。
样例
输入: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
输入:nums = [5,2,4,6,6,3], queries = [[12,4],[8,1],[6,3]]
输出:[15,-1,5]
限制
1 <= nums.length, queries.length <= 10^5
queries[i].length == 2
0 <= nums[j], x_i, m_i <= 10^9
算法
(01 Trie 树) $O((n + q) \log S)$
- 将给定的数组里的数字构造成一棵 01 Trie 树。由于最大的数字 $S$ 不超过 $10^9$ 则可以规定每个不同数字占用一个叶子节点,每一层表示一个二进制位,从根节点到叶子节点经过 30 条边。
- 在插入过程中,除根节点外的每个节点,都记录所有经过数字的最小值。
- 查询时,从根节点开始,优先考虑与 $x$ 在当前层不同的分支(因为产生的结果更大)。如果不同的分支存在,且选择不同分支后,到达节点中记录的最小值小于等于 $m$,则可以选择不同分支,答案累加 $2^h$。
- 否则,考虑相同的分支,也要经过最小值的验证。如果两个分支都不存在或者都不满足要求,则返回 -1。
时间复杂度
- 建树时,每个数字都经过 $O(\log S)$ 层。
- 查询时,每次也需要遍历 $O(\log S)$ 层。
- 故总时间复杂度为 $O((n + q) \log S)$。
空间复杂度
- 最坏情况下需要 $O(n \log S)$ 的额外空间存储 01 Trie 树。
C++ 代码
#define min(x, y) ((x) < (y) ? (x) : (y))
struct Node {
int mi;
Node *nxt[2];
Node() {
mi = INT_MAX;
nxt[0] = nxt[1] = NULL;
}
};
class Solution {
private:
Node *root;
void insert(int x) {
Node *p = root;
for (int i = 30; i >= 0; i--) {
int v = (x >> i) & 1;
if (p->nxt[v] == NULL) p->nxt[v] = new Node();
p = p->nxt[v];
p->mi = min(p->mi, x);
}
}
int query(int x, int m) {
Node *p = root;
int res = 0;
for (int i = 30; i >= 0; i--) {
int v = (x >> i) & 1;
if (p->nxt[v ^ 1] && p->nxt[v ^ 1]->mi <= m) {
res |= 1 << i;
p = p->nxt[v ^ 1];
} else if (p->nxt[v] && p->nxt[v]->mi <= m) {
p = p->nxt[v];
} else {
return -1;
}
}
return res;
}
public:
vector<int> maximizeXor(vector<int>& nums, vector<vector<int>>& queries) {
root = new Node();
for (int x : nums)
insert(x);
vector<int> ans(queries.size());
for (int i = 0; i < queries.size(); i++) {
int x = queries[i][0], m = queries[i][1];
ans[i] = query(x, m);
}
return ans;
}
};
mi 设置的真好
思路很奇妙