python:在两个数组之间交换元素的算法

Question

我正在分析计数example在 Codility 提出的 python 中

我不明白该算法最后一个循环(最后 5 行)中使用的逻辑。
有人可以帮忙吗？

问题:

You are given an integer m (1 < m < 1000000) and two non-empty, zero-indexed arrays A and B of n integers, a0, a1, ... , an−1 and b0, 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 array A equals the sum of elements in array B after the swap. By swap operation we mean picking one element from array A and one element from array B and exchanging them.

解决办法:

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

Answer 1

我建议您再次阅读练习中给出的解释。它已经解释了该算法的工作原理。但是，如果您仍然遇到问题，请拿一张纸和一些非常简单的示例数组，然后逐步解决该问题。

例如，让 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。

希望这有帮助。