我正在学习 Codility 计数课 ( https://codility.com/media/train/2-CountingElements.pdf ),我需要帮助来了解最快的解决方案。
我想知道为什么第 8 行中差值除以 2 d //= 2
?差异是否足以找到我们可以在数组之间交换的元素?
问题:
You are given an integer
m
(1 < m < 1000000
) and two non-empty, zero-indexed arraysA
andB
ofn
integers,a0
,a1
, ... ,an−1
andb0
,b1
, ... ,bn−1
respectively (0 < ai
,bi < m
). The goal is to check whether there is a swap operation which can be performed on these arrays in such a way that the sum of elements in arrayA
equals the sum of elements in arrayB
after the swap. By swap operation we mean picking one element from arrayA
and one element from arrayB
and exchanging them.
解决方法:
def fast_solution(A, B, m):
n = len(A)
sum_a = sum(A)
sum_b = sum(B)
d = sum_b - sum_a
if d % 2 == 1:
return False
d //= 2
count = counting(A, m)
for i in xrange(n):
if 0 <= B[i] - d and B[i] - d <= m and count[B[i] - d] > 0:
return True
return False
最佳答案
A[i
] 和 B[j]
之间的交换将 B[j]-A[i]
添加到 sum(A)
和从sum(B)
中减去相同的值;因此它影响总和的差 两倍 B[j]-A[i]
。
因此,将原始差异减半(在检查它是偶数之后——如果它是奇数,则没有交换将起作用!-)以形成可能交换的目标是正确的。
另请注意,它们提供的 counting
函数并不是现代 Python 的最佳选择——为避免重新发明“计数项目”的特定轮子,请参阅 https://docs.python.org/2/library/collections.html#collections.Counter对于 Python 2,或 https://docs.python.org/3/library/collections.html#collections.Counter适用于 Python 3。
关于python - Codility计数课,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/27581933/