用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。0XOR3=3和1XOR3=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]