我正在分析Codility提供的python中的example计数
我不了解此算法的最后一个循环(最后5行)中使用的逻辑。
有人可以帮忙吗?
问题:
系统会为您提供一个整数m
(1 < m < 1000000
)和两个非空,
零索引数组A
和B
的n
整数a0
,a1
,...,
an−1
和b0
,b1
,...,bn−1
(0 < ai
,bi < m
)。
目的是检查是否存在可以进行
对这些数组执行以下操作:
交换之后,数组A
等于数组B
中元素的总和。通过
交换操作,我们的意思是从数组A
中选择一个元素,然后选择一个
数组B
中的元素并交换它们。
解决方案:
def counting(A, m):
n = len(A)
count = [0] * (m + 1)
for k in xrange(n):
count[A[k]] += 1
return count
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 = [6, 6, 1, 2, 3]
和B = [1, 5, 3, 2, 1]
。
现在让我们看一下算法。
我假设您了解此方法的工作原理:
def counting(A, m):
n = len(A)
count = [0] * (m + 1)
for k in xrange(n):
count[A[k]] += 1
return count
如练习中所述,它仅返回带有计数的列表。对于列表A和m = 10,它将返回:
[0, 1, 1, 1, 0, 0, 2, 0, 0, 0, 0]
然后我们遍历主要方法
fast_solution(A, B, m)
:n = 11
(将在循环中使用)A的总和等于
18
,B的总和等于12
。差异
d
是-6
(sum_b-sum_a),它是偶数。请注意,如果差异为奇数,则没有交换可用,结果为False。然后
d
除以2
。变为-3
。对于A,我们得到计数
[0, 1, 1, 1, 0, 0, 2, 0, 0, 0, 0]
(如前所述)。然后,我们仅使用
xrange
遍历列表B并检查条件(循环从0开始直至不包括11)。让我们逐步检查它:i = 0
,B[0] - (-3)
是1 + 3 = 4
。 4大于或等于0且小于或等于10(请记住,我们选择m
为10
)。但是,count[4]
为0,并且不大于0(请注意,列表count
从索引0
开始)。条件失败,我们走得更远。i = 1
,B[1] - (-3)
是5 + 3 = 8
。 8大于或等于0且小于或等于10。但是,count[8]
为0,条件失败。i = 2
,B[2] - (-3)
是3 + 3 = 6
。 6大于0且小于10。同时count[6]
为2且大于0。因此我们找到了数字。循环停止,返回True。这意味着B中有这样的数字可以与A中的数字互换,因此A的总和等于B的总和。实际上,如果我们将A中的6与B中的3互换,则它们的总和等于15。希望这可以帮助。
关于python - python:在两个数组之间交换元素的算法,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/40275125/