用Python中数组中的元素找到最大异或的程序
假设我们有一个名为 nums 的数组，其中包含非负值。我们还有另一个称为查询的数组，其中查询 [i] 有一对 (xi, mi)。第 i 个查询的答案是 xi 和任何小于或等于 mi 的 nums 元素的最大按位异或值。如果 nums 中的所有元素都大于 mi，则答案为 -1。所以我们必须找到一个数组答案，其中答案的大小与查询的大小相同，而 answer[i] 是第 i 个查询的答案。
因此，如果输入类似于 nums = [0,1,2,3,4] 查询 = [[3,1],[1,3],[5,6]]，那么输出将是 [3, 3,7]，因为
0 和 1 不大于 1。0 XOR 3 = 3 和 1 XOR 3 = 2，这里这两者中较大的是 3。
1 异或 2 = 3。
5 异或 2 = 7。
示例
让我们看下面的实现来更好地理解
def solve(nums, queries):m, n = len(nums), len(queries)
queries = sorted(((i, x, limit) for i, (x, limit) in
enumerate(queries)), key=lambda x: x[2])
nums = sorted(nums)
res = [0] * n
for k in range(31, -1, -1):
prefixes = set()
j = 0
for i, x, limit in queries:
while j <= m - 1 and nums[j] <= limit:
prefixes.add(nums[j] >> k)
j += 1
if not prefixes:
res[i] = -1
else:
res[i] <<= 1
target = res[i] ^ 1
if (x >> k) ^ target in prefixes:
res[i] = target
return res
nums = [0,1,2,3,4]
queries = [[3,1],[1,3],[5,6]]
print(solve(nums, queries))
输入
[0,1,2,3,4], [[3,1],[1,3],[5,6]]输出结果
[3, 3, 7]
以上是 用Python中数组中的元素找到最大异或的程序 的全部内容， 来源链接： utcz.com/z/355068.html
