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

我不了解此算法的最后一个循环(最后5行)中使用的逻辑。
 有人可以帮忙吗?

问题:


  系统会为您提供一个整数m1 < m < 1000000)和两个非空,
  零索引数组ABn整数a0a1,...,
  an−1b0b1,...,bn−10 < aibi < 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 = 0B[0] - (-3)1 + 3 = 4。 4大于或等于0且小于或等于10(请记住,我们选择m10)。但是,count[4]为0,并且不大于0(请注意,列表count从索引0开始)。条件失败,我们走得更远。

i = 1B[1] - (-3)5 + 3 = 8。 8大于或等于0且小于或等于10。但是,count[8]为0,条件失败。

i = 2B[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/

10-12 03:05
查看更多