代码之家 › 专栏 › 技术社区 › Elimination

在A和B之间交换元素以获得和相等

algorithm python

Elimination · 技术社区 · 7 年前

我们有两个长度相等的数组, A 和 B .而且,每一个 i 以下内容: 0 <= a_i, b_i <= m 对于一些人 1<=m<= 1000000 .我们要检查在 A 还有一个术语 B 将使数组的和相等。

考虑以下解决方案:

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) # returns a mapping <integer, #occurrences in A>
  for i in range(n):
    if 0 <= B[i] - d and B[i] - d <= m and count[B[i] - d] > 0:
      return True
  return False

如果你能解释一下最后一个问题背后的原因,我会很高兴的。 if 条款。

Source of the problem

2 回复 | 直到 7 年前

Martijn Pieters 7 年前

如果存在这样的交换,那么两个值之间的差额必须是总和差额的一半。交换两个值意味着 二者都 列表将以相同的数量变化,一个向上,另一个向下。这两个变化必须加上交换前金额之间的差额,两个金额的变化值相同。( +d 和 -d ,或价值 delta,这是两个交换值之间的差异)。

首先,函数计算 d 作为和之间的增量,和增量。注意 sum_a 可以是 更大的 比 sum_b ,此时的结果 sum_b - sum_a 为负。这就意味着 B 小于中的目标值 A 交换会减少 总结 增加 总结 使他们平等。如果和delta的奇偶性为 古怪的 而不是偶数,您将永远找不到值delta是和delta的一半,因此函数返回 False 在这一点上。的最终值 D 是价值 delta,两个交换值之间的差异量。记住,值delta是和delta的一半。

算法计算所有值 A ,然后测试中的所有值 B .只有在 A 和 B 如果有的话一价值 B 不同之处在于 D 从一价值 A .价值 A 交换 B 需要等于 b_value - d .对于一个否定的 D ( sum_a > sum_b )那会使 b_value 小一点,积极点 D 那就需要 B_值 成为更大的数字。

这个 if 测试查看是否在 B - d 在中可用 A ,但它首先测试 B值-D 仍在[0-m]范围内:

0 <= B[i] - d 测试在a中查找的数字是否仍为正数。
B[i] - d <= m 测试所需数量是否仍不大于 m 可能是如果 B[i] 很接近,而且 D 为负。
count 包含中数字的计数 A ;如果 count[B[i] - d] > 0 如果为真,则A中至少有一个这样的数字。这是一个可以交换的数字。

需要进行范围测试,因为 counted 列表仅保留从0到m(含0到m)的数字计数,不包含负数或大于 米 .

该函数可以通过使用集合而不是计数函数来改进。不需要知道数字出现在 A 就这样存在 .这将使边界检查过时,因为超出界限的数字不会出现在 A .

一旦我们有了a的一组值,我们就可以测试这个集合是否是 disjoint 从应用了增量的B值集,使用 set.isdisjoint() 以下内容:

def faster_solution(A, B, m=None):  # m is ignored in this version
    delta = sum(A) - sum(B)
    if delta % 2 == 1:
        return False
    delta //= 2
    return not set(A).isdisjoint(b - delta for b in B)

如果在 A 等于一价值 B 减去delta。python将只在 b - delta for b in B 循环直到找到匹配(此时集合不分离,并且 not 或者循环已耗尽,因此在 A 发现这些集合是不相交的。

这个 counter() 显示的函数还有另一个问题:它需要的内存比需要的要多,而且与 collections.Counter() object 在中实现了一个优化循环来进行计数。A Counter() 使用字典(哈希映射)仅存储大于0的计数。

上面的设置解决方案比“快速解决方案”简单易行:

>>> import timeit, random
>>> m = 1000000
>>> testdata = [random.randrange(m + 1) for _ in range(1000)]
>>> testinputs = (testdata[:], testdata[:])
>>> random.shuffle(testinputs[0])  # The order of A differs from B
>>> testinputs[1][-1] -= testinputs[1][-1] // 2  # now the two sums differ by an even amount, guaranteed to be in range
>>> assert testinputs[1][-1] > 0  # make sure the original random value was not 0 or 1.
>>> # note: It's the *last value in B* that makes it possible to swap;
... # this is one of two worst-case scenarios (the other is even-delta-no-swap).
...
>>> assert fast_solution(*testinputs, m)    # the original finds a solution
>>> assert faster_solution(*testinputs, m)  # my version finds a solution
>>> timeit.timeit("f(*ab, m)", "from __main__ import fast_solution as f, testinputs as ab, m", number=1000)
2.3270092820748687
>>> timeit.timeit("f(*ab, m)", "from __main__ import faster_solution as f, testinputs as ab, m", number=1000)
0.13949943508487195

不使用计数器,使用python的set功能使输入长度为1000的数据快17倍!

故事的寓意是:使用你所选择语言中的最佳工具,批判性地思考解决问题实际需要什么。python的内置类型和操作通常可以避免在python字节码中运行关键的循环,从而显著减少了算法的常量时间因素。

fafl 7 年前

结尾的for循环搜索 B 数组。作为索引处的交换元素 i 必须满足两个条件:

B[i] - d 必须介于 0 和 m .你可以想象 2 * d 多少钱? sum(B) 大于 sum(A) ,所以通过交换 B[i] 具有 B[I]-D型 ,数组 A 带增益 d 和数组 B 将丢失它,增加差异 2*d天
B[I]-D型 必须存在于

重新定义对理解是不好的 d = d / 2 在代码的中间:)