与数组中元素的最大 XOR |力扣
Maximum XOR With an Element From Array | Leetcode
我在练习 Leetcode 时遇到了这个问题。
问题陈述（link）：
You are given an array nums consisting of non-negative integers.
You are also given a queries array, where queries[i] = [xi, mi].
The answer to the ith query is the maximum bitwise XOR value of xi and any element of nums that does not exceed mi.
In other words, the answer is max(nums[j] XOR xi) for all j such that nums[j] <= mi.
If all elements in nums are larger than mi, then the answer is -1.
Return an integer array answer where answer.length == queries.length and answer[i] is the answer to the ith query.
限制条件：
1 <= nums.length, queries.length <= 10^5
queries[i].length == 2
0 <= nums[j], xi, mi <= 10^9
我使用 trie 方法解决了这个问题，然后去讨论部分查看其他解决方案。在那里，我遇到了这个解决方案 (link):
class Solution {
public:
vector<int> maximizeXor(vector<int>& nums, vector<vector<int>>& queries) {
const int n = nums.size(), q = queries.size();
vector<int> ans(q, -1);
sort(nums.begin(), nums.end());
for (int i = 0; i < q; i++) {
const int x = queries[i][0], m = queries[i][1];
if (m < nums[0]) continue;
int end = upper_bound(nums.begin(), nums.end(), m) - nums.begin();
int start = 0;
int k = 0, cur = 0;
for (int bit = 31; bit >= 0; bit--) {
if (x & (1 << bit)) { // hope A[i] this bit == 0
if (!(nums[start] & (1 << bit))) {
k |= 1 << bit;
end = lower_bound(nums.begin() + start, nums.begin() + end, cur | (1 << bit)) - nums.begin();
} else {
cur |= 1 << bit;
}
} else { // hope: A[i] this bit == 1
if (start <= end - 1 && (nums[end - 1] & (1 << bit))) {
k |= 1 << bit;
cur |= 1 << bit;
start = lower_bound(nums.begin() + start, nums.begin() + end, cur) - nums.begin();
}
}
}
ans[i] = k;
}
return ans;
}
};
很遗憾，我无法理解这个解决方案。如果有人能对此解决方案给出正确的解释（主要是在循环位时），我将不胜感激。
此实现存在一些问题。 start 和 end 应该保持迭代器，它们可以直接使用而不需要 adding/subtracting nums.begin() 一直。我们谈论的是非负整数，所以只要它们符合正常 int 无论如何第一位都是 0，所以我们应该从 int bit = 30 开始跳过一个不必要的迭代。对于整数和迭代器，start <= end - 1 比 start < end 更好。该代码由一个函数组成，绝对不需要 class ，因此应该更喜欢名称空间。应用这些更改后，代码将如下所示：
namespace Solution
{
// as EXACTLY two values, std::pair is more appropriate
// we are not modifying queries, so should be accepted as const
std::vector<int> maximizeXor
(
std::vector<int>& nums, std::vector<std::pair<int, int>>const& queries
)
{
const int q = queries.size();
std::vector<int> ans(q, -1);
sort(nums.begin(), nums.end());
// remove duplicates:
// -> less numbers to iterate over
nums.erase(unique(nums.begin(), nums.end()), nums.end());
for (int i = 0; i < q; ++i)
{
int const x = queries[i].first, m = queries[i].second;
// we have a sorted array, remember?
// if first value is larger than the query maximum, then there are no
// corresponding numbers – and as the vector is initialised to -1
// anyway, the appropriate value is there already so we can simply skip
if (m < nums[0])
{
continue;
}
// using iterators pointing at the appropriate indices
auto end = upper_bound(nums.begin(), nums.end(), m);
auto start = nums.begin();
int /*k = 0,*/ cur = 0;
// intention is to check each bit of x
// modifying the loop!
//for (int bit = 30; bit >= 0; bit--)
int const MaxBit = 1 << sizeof(int) * CHAR_BIT - 2;
for (int bit = MaxBit; start != prev(end); bit >>= 1)
{
// OK; fixing an issue and adding some tricks to handle the loop
// a bit cleverer...
// sizeof(int) * CHAR_BIT: int is NOT guaranteed to have exactly
// 32 bits! if you want to be on the safe side, either calculate
// as above or use int32_t instead
// changed abort condition:
// I modified the algorithm slightly such that we can break early
// unique'ing the vector allows us to drop the original
// condition bit >= 0 entirely, this will be explained later
// I store the bit-MASK in bit now, now we do not have to
// calculate it again and again (1 << bit)
if (x & bit)
{
// so x has a 1-bit at bit index 'bit'
// in the range yet to be considered we have two groups of
// numbers:
// 1. those having a 0-bit at bit-index 'bit'
// 2. those having a 1-bit
// if we compare single bits, we get:
// x = *1***
// num = *0*** XOR: *1***
// num = *1*** XOR: *0***
// IF now there are numbers with a zero bit at all, then one
// of these will produce the maximum, whereas those with a
// 1-bit cannot asnumbers are sorted, we can just check very
// first value of the range:
// any number having a 1-bit at the same bit index will produce
// a zero-bit – thus these numbers CANNOT produce the maximum
if (!(*start & bit))
{
// bits differ, remember?
// thus the XOR will have a one-bit we store right now
// actually, we do NOT need that, we can handle that cleverer
//k |= 1 << bit;
// instead, I handle this with the NEW loop condition
// fine – there ARE numbers with zero-bits, so remove all
// numbers with 1-bit from range; as they all are at the end
// of, we simply move this one towards front:
end = lower_bound(start, end, cur | bit);
// cur contains those bits of the number producing the
// maximum that have been evaluated so far, it is a
// lower bound for – we do NOT modify it, but we can
// calculate a new upper bound from!
}
else
{
// well, there is no such number with a 0-bit
// we cannot move end or start position
cur |= bit;
}
}
else
{
// analogously:
// x = *0***
// num = *0*** XOR: *0***
// num = *1*** XOR: *1***
// so all members having a 1-bit are of interest – IF there
// are – and we can skip those numbers with 0-bit at the
// beginning
// if there are, then they are at the very end
// 'end' iterator points to one past, so we need predecessor
if (/*start < end &&*/ *prev(end) & bit)
{
// first condition is handled in the loop now
// as above: we can handle that cleverer
//k |= 1 << bit;
// now current mask NEEDS the one-bit
cur |= bit;
start = lower_bound(start, end, cur);
}
}
// with unchanged loop it was not possible to break early as k still
// needed to be calculated
//ans[i] = k;
// with or without early break, we can always:
ans[i] = *start ^ x;
// with every iteration, we extend the bit mask 'cur' the numbers
// have to match with by one bit (either the 0 gets confirmed
// or replaced by a 1).
// After 31 iterations (sign bit is ignored as we only have
// positive integers), *all* bits are defined (if we had omitted
// the early breaks we could have calculated
// ans[i] = cur ^ x; as well...).
// so all numbers that yet might have remained in the valid range
// must match this pattern, i. e. be equal. However as unique-ing,
// there is exactly one single value left...
}
}
return ans;
}
} // namespace Solution
请注意 std::lower_bound 具有（提供随机访问迭代器，与 std::vector 一样）复杂度 O(log(n))，因此执行单个查询具有 O(log(n)) n 是数字的数量。加上排序和查询 m 次的开销，与复杂度为 O(m*n) 的 'naive' 次迭代相比，我们得到的总复杂度为 O(n*log(n) + m*log(n)) = O((n+m)*log(n))。如果 m 与 n 的大小相似或更大，我们就具有复杂性优势（已经在原始变体中，我的调整只是 trim 了一点常量，但不改变复杂性）。
我在练习 Leetcode 时遇到了这个问题。
问题陈述（link）：
You are given an array nums consisting of non-negative integers.
You are also given a queries array, where queries[i] = [xi, mi].
The answer to the ith query is the maximum bitwise XOR value of xi and any element of nums that does not exceed mi.
In other words, the answer is max(nums[j] XOR xi) for all j such that nums[j] <= mi.
If all elements in nums are larger than mi, then the answer is -1.
Return an integer array answer where answer.length == queries.length and answer[i] is the answer to the ith query.
限制条件：
1 <= nums.length, queries.length <= 10^5
queries[i].length == 2
0 <= nums[j], xi, mi <= 10^9
我使用 trie 方法解决了这个问题，然后去讨论部分查看其他解决方案。在那里，我遇到了这个解决方案 (link):
class Solution {
public:
vector<int> maximizeXor(vector<int>& nums, vector<vector<int>>& queries) {
const int n = nums.size(), q = queries.size();
vector<int> ans(q, -1);
sort(nums.begin(), nums.end());
for (int i = 0; i < q; i++) {
const int x = queries[i][0], m = queries[i][1];
if (m < nums[0]) continue;
int end = upper_bound(nums.begin(), nums.end(), m) - nums.begin();
int start = 0;
int k = 0, cur = 0;
for (int bit = 31; bit >= 0; bit--) {
if (x & (1 << bit)) { // hope A[i] this bit == 0
if (!(nums[start] & (1 << bit))) {
k |= 1 << bit;
end = lower_bound(nums.begin() + start, nums.begin() + end, cur | (1 << bit)) - nums.begin();
} else {
cur |= 1 << bit;
}
} else { // hope: A[i] this bit == 1
if (start <= end - 1 && (nums[end - 1] & (1 << bit))) {
k |= 1 << bit;
cur |= 1 << bit;
start = lower_bound(nums.begin() + start, nums.begin() + end, cur) - nums.begin();
}
}
}
ans[i] = k;
}
return ans;
}
};
很遗憾，我无法理解这个解决方案。如果有人能对此解决方案给出正确的解释（主要是在循环位时），我将不胜感激。
此实现存在一些问题。 start 和 end 应该保持迭代器，它们可以直接使用而不需要 adding/subtracting nums.begin() 一直。我们谈论的是非负整数，所以只要它们符合正常 int 无论如何第一位都是 0，所以我们应该从 int bit = 30 开始跳过一个不必要的迭代。对于整数和迭代器，start <= end - 1 比 start < end 更好。该代码由一个函数组成，绝对不需要 class ，因此应该更喜欢名称空间。应用这些更改后，代码将如下所示：
namespace Solution
{
// as EXACTLY two values, std::pair is more appropriate
// we are not modifying queries, so should be accepted as const
std::vector<int> maximizeXor
(
std::vector<int>& nums, std::vector<std::pair<int, int>>const& queries
)
{
const int q = queries.size();
std::vector<int> ans(q, -1);
sort(nums.begin(), nums.end());
// remove duplicates:
// -> less numbers to iterate over
nums.erase(unique(nums.begin(), nums.end()), nums.end());
for (int i = 0; i < q; ++i)
{
int const x = queries[i].first, m = queries[i].second;
// we have a sorted array, remember?
// if first value is larger than the query maximum, then there are no
// corresponding numbers – and as the vector is initialised to -1
// anyway, the appropriate value is there already so we can simply skip
if (m < nums[0])
{
continue;
}
// using iterators pointing at the appropriate indices
auto end = upper_bound(nums.begin(), nums.end(), m);
auto start = nums.begin();
int /*k = 0,*/ cur = 0;
// intention is to check each bit of x
// modifying the loop!
//for (int bit = 30; bit >= 0; bit--)
int const MaxBit = 1 << sizeof(int) * CHAR_BIT - 2;
for (int bit = MaxBit; start != prev(end); bit >>= 1)
{
// OK; fixing an issue and adding some tricks to handle the loop
// a bit cleverer...
// sizeof(int) * CHAR_BIT: int is NOT guaranteed to have exactly
// 32 bits! if you want to be on the safe side, either calculate
// as above or use int32_t instead
// changed abort condition:
// I modified the algorithm slightly such that we can break early
// unique'ing the vector allows us to drop the original
// condition bit >= 0 entirely, this will be explained later
// I store the bit-MASK in bit now, now we do not have to
// calculate it again and again (1 << bit)
if (x & bit)
{
// so x has a 1-bit at bit index 'bit'
// in the range yet to be considered we have two groups of
// numbers:
// 1. those having a 0-bit at bit-index 'bit'
// 2. those having a 1-bit
// if we compare single bits, we get:
// x = *1***
// num = *0*** XOR: *1***
// num = *1*** XOR: *0***
// IF now there are numbers with a zero bit at all, then one
// of these will produce the maximum, whereas those with a
// 1-bit cannot asnumbers are sorted, we can just check very
// first value of the range:
// any number having a 1-bit at the same bit index will produce
// a zero-bit – thus these numbers CANNOT produce the maximum
if (!(*start & bit))
{
// bits differ, remember?
// thus the XOR will have a one-bit we store right now
// actually, we do NOT need that, we can handle that cleverer
//k |= 1 << bit;
// instead, I handle this with the NEW loop condition
// fine – there ARE numbers with zero-bits, so remove all
// numbers with 1-bit from range; as they all are at the end
// of, we simply move this one towards front:
end = lower_bound(start, end, cur | bit);
// cur contains those bits of the number producing the
// maximum that have been evaluated so far, it is a
// lower bound for – we do NOT modify it, but we can
// calculate a new upper bound from!
}
else
{
// well, there is no such number with a 0-bit
// we cannot move end or start position
cur |= bit;
}
}
else
{
// analogously:
// x = *0***
// num = *0*** XOR: *0***
// num = *1*** XOR: *1***
// so all members having a 1-bit are of interest – IF there
// are – and we can skip those numbers with 0-bit at the
// beginning
// if there are, then they are at the very end
// 'end' iterator points to one past, so we need predecessor
if (/*start < end &&*/ *prev(end) & bit)
{
// first condition is handled in the loop now
// as above: we can handle that cleverer
//k |= 1 << bit;
// now current mask NEEDS the one-bit
cur |= bit;
start = lower_bound(start, end, cur);
}
}
// with unchanged loop it was not possible to break early as k still
// needed to be calculated
//ans[i] = k;
// with or without early break, we can always:
ans[i] = *start ^ x;
// with every iteration, we extend the bit mask 'cur' the numbers
// have to match with by one bit (either the 0 gets confirmed
// or replaced by a 1).
// After 31 iterations (sign bit is ignored as we only have
// positive integers), *all* bits are defined (if we had omitted
// the early breaks we could have calculated
// ans[i] = cur ^ x; as well...).
// so all numbers that yet might have remained in the valid range
// must match this pattern, i. e. be equal. However as unique-ing,
// there is exactly one single value left...
}
}
return ans;
}
} // namespace Solution
请注意 std::lower_bound 具有（提供随机访问迭代器，与 std::vector 一样）复杂度 O(log(n))，因此执行单个查询具有 O(log(n)) n 是数字的数量。加上排序和查询 m 次的开销，与复杂度为 O(m*n) 的 'naive' 次迭代相比，我们得到的总复杂度为 O(n*log(n) + m*log(n)) = O((n+m)*log(n))。如果 m 与 n 的大小相似或更大，我们就具有复杂性优势（已经在原始变体中，我的调整只是 trim 了一点常量，但不改变复杂性）。