数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究Python程序：查找数组中元素的最大异或值
假设我们有一个名为 nums 的数组，其中包含非负值。我们还有另一个名为 queries 的数组，其中 queries[i] 包含一个对 (xi, mi)。第 i 个查询的答案是 xi 与 nums 中任何小于或等于 mi 的元素进行按位异或运算的最大值。如果 nums 中的所有元素都大于 mi，则答案为 -1。因此，我们必须找到一个答案数组，其大小与查询的大小相同，并且 answer[i] 是第 i 个查询的答案。
因此，如果输入类似于 nums = [0,1,2,3,4] queries = [[3,1],[1,3],[5,6]]，则输出将为 [3,3,7]，因为
0 和 1 不大于 1。0 XOR 3 = 3 且 1 XOR 3 = 2，这里这两个数中较大的一个是 3。
1 XOR 2 = 3。
5 XOR 2 = 7。
为了解决这个问题，我们将遵循以下步骤 -
m := nums 的大小
n := queries 的大小
queries = 为每个索引 i 和查询中的对 (x, limit) 创建一个三元组 (i, x, limit)
根据 limit 对 queries 进行排序
nums := 对列表 nums 进行排序
res := 一个大小为 n 的数组，并用 0 填充
对于 k 从 31 到 0，递减 1，执行
prefixes := 一个新的集合
j := 0
对于查询中的每个索引 i 和值 (x, limit)，执行
当 j <= m - 1 且 nums[j] <= limit 时，执行
将 nums[j] 右移 k 位并插入到 prefixes 中
j := j + 1
如果 prefixes 为空，则
res[i] := -1
否则，
res[i] = res[i]/2 的商
target := res[i] XOR 1
如果 (x 右移 k 位后) XOR target 在 prefixes 中，则
res[i] := target
返回 res
示例
让我们看看以下实现以获得更好的理解
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]
247 次查看
