计算具有给定异或的所有对

Question

给定一个大小为 N 的列表。找出满足 A[i] XOR A[j] = x 且 1 <= i < j <= N 的 (i, j) 对的数量。

输入：列表 = [3, 6, 8, 10, 15, 50], x = 5

输出：2

解释：(3 ^ 6) = 5 和 (10 ^ 15) = 5

这是我的代码（暴力破解）：

import itertools
n=int(input())
pairs=0
l=list(map(int,raw_input().split()))
q=[x for x in l if x%2==0]
p=[y for y in l if y%2!=0]
for a, b in itertools.combinations(q, 2):
    if (a^b!=2) and ((a^b)%2==0) and (a!=b):
        pairs+=1
for a, b in itertools.combinations(p, 2):
    if (a^b!=2) and ((a^b)%2==0) and (a!=b):
        pairs+=1
print pairs

如何在 python 的复杂度 O(n) 中更有效地做到这一点？

Answer 1

观察如果 A[i]^A[j] == x，这意味着 A[i]^x == A[j] 和 A[j]^x == A[i]。

因此，O(n) 解决方案是遍历关联映射 (dict)，其中每个键都是 A 中的一个项目，每个值都是该项目的相应计数.然后，对于每个项目，计算 A[i]^x，并查看 A[i]^x 是否在地图中。如果它在地图中是，这意味着 A[i]^A[j] == x for some j。由于我们有一个地图，其中所有项目的计数等于 A[j]，因此对的总数将为 num_Ai * num_Aj。请注意，每个元素将被计算两次，因为 XOR 是可交换的（即 A[i]^A[j] == A[j]^A[i]），因此我们必须将最终计数除以 2，因为我们对每一对进行了双重计算。

def create_count_map(lst):
    result = {}
    for item in lst:
        if item in result:
            result[item] += 1
        else:
            result[item] = 1
    return result

def get_count(lst, x):
    count_map = create_count_map(lst)
    total_pairs = 0
    for item in count_map:
        xor_res = item ^ x
        if xor_res in count_map:
            total_pairs += count_map[xor_res] * count_map[item]
    return total_pairs // 2

print(get_count([3, 6, 8, 10, 15, 50], 5))
print(get_count([1, 3, 1, 3, 1], 2))

输出

2
6

随心所欲。

为什么是 O(n)？

正在将 list 转换为 dict s.t。 dict 包含列表中每个项目的计数是 O(n) 时间。

计算item ^ x是O(1)时间，计算这个结果是否在dict也是O(1)时间。 dict 键访问也是 O(1)，两个元素的乘法也是如此。我们做了 n 次所有这些，因此循环的时间为 O(n)。

O(n) + O(n) 减少到 O(n) 时间。

已编辑以正确处理重复项。

Answer 2

接受的答案没有给出 X=0 的正确结果。此代码处理那个微小的错误。您也可以修改它以获得其他值的答案。

def calculate(a) :

# Finding the maximum of the array
maximum = max(a)

# Creating frequency array
# With initial value 0
frequency = [0 for x in range(maximum + 1)]

# Traversing through the array 
for i in a :

    # Counting frequency
    frequency[i] += 1

answer = 0

# Traversing through the frequency array
for i in frequency :

    # Calculating answer
    answer = answer + i * (i - 1) // 2

return answer

计算具有给定异或的所有对

Count all pairs with given XOR

python

xor