CountingElements 解决方案

Question

我正在尝试了解问题和提供的解决方案。却无法完全掌握 https://codility.com/media/train/2-CountingElements.pdf

You are given an integer m (1 <= m <= 1 000 000) 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 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

(0 <= ai , bi <= m) 这是否意味着 (0<=ai<=bi<=m)？这个等式是如何表示的？鉴于解决方案，我认为应该是这种情况。

这部分背后的逻辑是什么？

 if d % 2 == 1:
 return False
 d //= 2

感谢您的帮助

Answer 1

what is the logic behind this section?

if d % 2 == 1: return False d //= 2

道理很简单。

说明

这可以通过以下几个简单的步骤轻松完成：

Sum 1 = sum of (a0, a1, . . . , an−1)

花费的时间O(N)

Sum 2 = sum of (b0, b1, . . . , bn−1)

花费的时间O(N)

假设解对是(ai,bi)。这意味着：Sum 2 + ai - bi = Sum 1 + bi - ai，这意味着：

ai - bi = (Sum 1 - Sum 2)/2  // equation 1

上面的等式表明总和的差值必须能被 2 整除才能存在解，因为数组是由整数组成的。

看起来我们可以使用 binary search 。现在对其中一个数组（比如 A）进行排序，为二分查找做准备。所用时间 O(NlogN)。现在遍历数组B，对于每个bi，ai的值可以从上面的等式中找到。因此计算 ai 并使用二进制搜索检查它是否存在于数组 A 中。这也需要 O(NlogN)，因为在最坏的情况下我们最多应用二分查找 N 次。

备选方案

另一种解决方案可能是利用 hash table 数据结构，它需要 O(N) 时间，但 space 复杂度为 O(N) 。

CountingElements 解决方案

CountingElements solution

algorithm

counting

compare-and-swap