class Solution {
public:
vector<int> maximizeXor(vector<int>& nums, vector<vector<int>>& queries) {
}
};
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 <= 105queries[i].length == 20 <= nums[j], xi, mi <= 109原站题解
golang 解法, 执行用时: 396 ms, 内存消耗: 38.7 MB, 提交时间: 2023-09-27 11:24:21
const L = 30
type trie struct {
children [2]*trie
}
func (t *trie) insert(val int) {
node := t
for i := L - 1; i >= 0; i-- {
bit := val >> i & 1
if node.children[bit] == nil {
node.children[bit] = &trie{}
}
node = node.children[bit]
}
}
func (t *trie) getMaxXor(val int) (ans int) {
node := t
for i := L - 1; i >= 0; i-- {
bit := val >> i & 1
if node.children[bit^1] != nil {
ans |= 1 << i
bit ^= 1
}
node = node.children[bit]
}
return
}
// 离线查询 + 字典树
func maximizeXor(nums []int, queries [][]int) []int {
sort.Ints(nums)
for i := range queries {
queries[i] = append(queries[i], i)
}
sort.Slice(queries, func(i, j int) bool { return queries[i][1] < queries[j][1] })
ans := make([]int, len(queries))
t := &trie{}
idx, n := 0, len(nums)
for _, q := range queries {
x, m, qid := q[0], q[1], q[2]
for idx < n && nums[idx] <= m {
t.insert(nums[idx])
idx++
}
if idx == 0 { // 字典树为空
ans[qid] = -1
} else {
ans[qid] = t.getMaxXor(x)
}
}
return ans
}
golang 解法, 执行用时: 508 ms, 内存消耗: 40.6 MB, 提交时间: 2023-09-27 11:23:51
const L = 30
type trie struct {
children [2]*trie
min int
}
func (t *trie) insert(val int) {
node := t
if val < node.min {
node.min = val
}
for i := L - 1; i >= 0; i-- {
bit := val >> i & 1
if node.children[bit] == nil {
node.children[bit] = &trie{min: val}
}
node = node.children[bit]
if val < node.min {
node.min = val
}
}
}
func (t *trie) getMaxXorWithLimit(val, limit int) (ans int) {
node := t
if node.min > limit {
return -1
}
for i := L - 1; i >= 0; i-- {
bit := val >> i & 1
if node.children[bit^1] != nil && node.children[bit^1].min <= limit {
ans |= 1 << i
bit ^= 1
}
node = node.children[bit]
}
return
}
func maximizeXor(nums []int, queries [][]int) []int {
t := &trie{min: math.MaxInt32}
for _, val := range nums {
t.insert(val)
}
ans := make([]int, len(queries))
for i, q := range queries {
ans[i] = t.getMaxXorWithLimit(q[0], q[1])
}
return ans
}
python3 解法, 执行用时: 6632 ms, 内存消耗: 259.3 MB, 提交时间: 2023-09-27 11:23:32
# 在线查询 + 字典树
class Trie:
L = 30
def __init__(self):
self.left = None
self.right = None
self.min_value = float("inf")
def insert(self, val: int):
node = self
node.min_value = min(node.min_value, val)
for i in range(Trie.L, -1, -1):
bit = (val >> i) & 1
if bit == 0:
if not node.left:
node.left = Trie()
node = node.left
else:
if not node.right:
node.right = Trie()
node = node.right
node.min_value = min(node.min_value, val)
def getMaxXorWithLimit(self, val: int, limit: int) -> int:
node = self
if node.min_value > limit:
return -1
ans = 0
for i in range(Trie.L, -1, -1):
bit = (val >> i) & 1
check = False
if bit == 0:
if node.right and node.right.min_value <= limit:
node = node.right
check = True
else:
node = node.left
else:
if node.left and node.left.min_value <= limit:
node = node.left
check = True
else:
node = node.right
if check:
ans |= 1 << i
return ans
class Solution:
def maximizeXor(self, nums: List[int], queries: List[List[int]]) -> List[int]:
t = Trie()
for val in nums:
t.insert(val)
q = len(queries)
ans = [0] * q
for i, (x, m) in enumerate(queries):
ans[i] = t.getMaxXorWithLimit(x, m)
return ans
python3 解法, 执行用时: 5996 ms, 内存消耗: 259.3 MB, 提交时间: 2023-09-27 11:23:04
# 离线查询 + 字典树
class Trie:
L = 30
def __init__(self):
self.left = None
self.right = None
def insert(self, val: int):
node = self
for i in range(Trie.L, -1, -1):
bit = (val >> i) & 1
if bit == 0:
if not node.left:
node.left = Trie()
node = node.left
else:
if not node.right:
node.right = Trie()
node = node.right
def getMaxXor(self, val: int) -> int:
ans, node = 0, self
for i in range(Trie.L, -1, -1):
bit = (val >> i) & 1
check = False
if bit == 0:
if node.right:
node = node.right
check = True
else:
node = node.left
else:
if node.left:
node = node.left
check = True
else:
node = node.right
if check:
ans |= 1 << i
return ans
class Solution:
def maximizeXor(self, nums: List[int], queries: List[List[int]]) -> List[int]:
n, q = len(nums), len(queries)
nums.sort()
queries = sorted([(x, m, i) for i, (x, m) in enumerate(queries)], key=lambda query: query[1])
ans = [0] * q
t = Trie()
idx = 0
for x, m, qid in queries:
while idx < n and nums[idx] <= m:
t.insert(nums[idx])
idx += 1
if idx == 0:
# 字典树为空
ans[qid] = -1
else:
ans[qid] = t.getMaxXor(x)
return ans
java 解法, 执行用时: 128 ms, 内存消耗: 111.9 MB, 提交时间: 2023-09-27 11:22:05
// 离线查询 + 字典树
class Solution {
public int[] maximizeXor(int[] nums, int[][] queries) {
Arrays.sort(nums);
int numQ = queries.length;
int[][] newQueries = new int[numQ][3];
for (int i = 0; i < numQ; ++i) {
newQueries[i][0] = queries[i][0];
newQueries[i][1] = queries[i][1];
newQueries[i][2] = i;
}
Arrays.sort(newQueries, new Comparator<int[]>() {
public int compare(int[] query1, int[] query2) {
return query1[1] - query2[1];
}
});
int[] ans = new int[numQ];
Trie trie = new Trie();
int idx = 0, n = nums.length;
for (int[] query : newQueries) {
int x = query[0], m = query[1], qid = query[2];
while (idx < n && nums[idx] <= m) {
trie.insert(nums[idx]);
++idx;
}
if (idx == 0) { // 字典树为空
ans[qid] = -1;
} else {
ans[qid] = trie.getMaxXor(x);
}
}
return ans;
}
}
class Trie {
static final int L = 30;
Trie[] children = new Trie[2];
public void insert(int val) {
Trie node = this;
for (int i = L - 1; i >= 0; --i) {
int bit = (val >> i) & 1;
if (node.children[bit] == null) {
node.children[bit] = new Trie();
}
node = node.children[bit];
}
}
public int getMaxXor(int val) {
int ans = 0;
Trie node = this;
for (int i = L - 1; i >= 0; --i) {
int bit = (val >> i) & 1;
if (node.children[bit ^ 1] != null) {
ans |= 1 << i;
bit ^= 1;
}
node = node.children[bit];
}
return ans;
}
}
// 在线查询 + 字典树
class Solution2 {
public int[] maximizeXor(int[] nums, int[][] queries) {
Trie2 trie = new Trie2();
for (int val : nums) {
trie.insert(val);
}
int numQ = queries.length;
int[] ans = new int[numQ];
for (int i = 0; i < numQ; ++i) {
ans[i] = trie.getMaxXorWithLimit(queries[i][0], queries[i][1]);
}
return ans;
}
}
class Trie2 {
static final int L = 30;
Trie2[] children = new Trie2[2];
int min = Integer.MAX_VALUE;
public void insert(int val) {
Trie2 node = this;
node.min = Math.min(node.min, val);
for (int i = L - 1; i >= 0; --i) {
int bit = (val >> i) & 1;
if (node.children[bit] == null) {
node.children[bit] = new Trie2();
}
node = node.children[bit];
node.min = Math.min(node.min, val);
}
}
public int getMaxXorWithLimit(int val, int limit) {
Trie2 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] != null && node.children[bit ^ 1].min <= limit) {
ans |= 1 << i;
bit ^= 1;
}
node = node.children[bit];
}
return ans;
}
}
cpp 解法, 执行用时: 804 ms, 内存消耗: 261.5 MB, 提交时间: 2023-09-27 11:20:09
// 离线询问 + 字典树
class Trie2 {
public:
const int L = 30;
Trie2* children[2] = {};
void insert(int val) {
Trie2* node = this;
for (int i = L - 1; i >= 0; --i) {
int bit = (val >> i) & 1;
if (node->children[bit] == nullptr) {
node->children[bit] = new Trie2();
}
node = node->children[bit];
}
}
int getMaxXor(int val) {
int ans = 0;
Trie2* node = this;
for (int i = L - 1; i >= 0; --i) {
int bit = (val >> i) & 1;
if (node->children[bit ^ 1] != nullptr) {
ans |= 1 << i;
bit ^= 1;
}
node = node->children[bit];
}
return ans;
}
};
class Solution2 {
public:
vector<int> maximizeXor(vector<int> &nums, vector<vector<int>> &queries) {
sort(nums.begin(), nums.end());
int numQ = queries.size();
for (int i = 0; i < numQ; ++i) {
queries[i].push_back(i);
}
sort(queries.begin(), queries.end(), [](auto &x, auto &y) { return x[1] < y[1]; });
vector<int> ans(numQ);
Trie2* t = new Trie2();
int idx = 0, n = nums.size();
for (auto &q : queries) {
int x = q[0], m = q[1], qid = q[2];
while (idx < n && nums[idx] <= m) {
t->insert(nums[idx]);
++idx;
}
if (idx == 0) { // 字典树为空
ans[qid] = -1;
} else {
ans[qid] = t->getMaxXor(x);
}
}
return ans;
}
};
// 在线询问 + 字典树
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;
}
};