问题描述
给定一个大小为 N 的列表.找出对 (i, j) 的数量,使得 A[i] XOR A[j] = x,并且 1
Given a list of size N. Find the number of pairs (i, j) such that A[i] XOR A[j] = x, and 1 <= i < j <= N.
输入:列表 = [3, 6, 8, 10, 15, 50], x = 5
Input : list = [3, 6, 8, 10, 15, 50], x = 5
输出:2
解释:(3 ^ 6) = 5 和 (10 ^ 15) = 5
Explanation : (3 ^ 6) = 5 and (10 ^ 15) = 5
这是我的代码(蛮力):
This is my code (brute force):
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
如何在复杂度为 O(n) 的 Python 中更有效地做到这一点?
how to do this more efficiently in a complexity of O(n) in python?
推荐答案
观察如果 A[i]^A[j] == x
,这意味着 A[i]^x == A[j]
和 A[j]^x == A[i]
.
Observe that if A[i]^A[j] == x
, this implies that A[i]^x == A[j]
and A[j]^x == A[i]
.
因此,O(n) 解决方案是遍历关联映射 (dict
),其中每个键是 A
中的一个项目,每个值是各自的项的计数.然后,对于每一项,计算A[i]^x
,看看A[i]^x
是否在地图中.如果它在地图中是,这意味着 A[i]^A[j] == x
对于 some j.由于我们有一个地图,其中包含等于
A[j]
的所有项目的计数,因此对的总数将为 num_Ai * num_Aj
.请注意,每个元素都会被计数两次,因为 XOR 是可交换的(即 A[i]^A[j] == A[j]^A[i]
),所以我们必须除以最后的计数 2,因为我们已经重复计算了每一对.
So, an O(n) solution would be to iterate through an associate map (
dict
) where each key is an item from A
and each value is the respective count of the item. Then, for each item, calculate A[i]^x
, and see if A[i]^x
is in the map. If it is in the map, this implies that A[i]^A[j] == x
for some j
. Since we have a map with the count of all items that equal A[j]
, the total number of pairs will be num_Ai * num_Aj
. Note that each element will be counted twice since XOR is commutative (i.e. A[i]^A[j] == A[j]^A[i]
), so we have to divide the final count by 2 since we've double counted each pair.
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.字典包含列表中每个项目的计数是 O(n) 时间.
Converting a
list
to a dict
s.t. the dict contains the count of each item in the list is O(n) time.
计算
item ^ x
是O(1)时间,计算这个结果是否在dict
中也是O(1)时间.dict
键访问也是 O(1),两个元素的乘法也是如此.我们做了 n 次,因此循环的时间为 O(n).
Calculating
item ^ x
is O(1) time, and calculating whether this result is in a dict
is also O(1) time. dict
key access is also O(1), and so is multiplication of two elements. We do all this n times, hence O(n) time for the loop.
O(n) + O(n) 减少到 O(n) 时间.
O(n) + O(n) reduces to O(n) time.
已编辑以正确处理重复项.
Edited to handle duplicates correctly.
这篇关于用给定的 XOR 计算所有对的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!