检查Python数组能否分成各对之和能被k整除

假设我们有一个数字数组和另一个数字k，我们必须检查给定的数组能否分成几对，使得每对的和都能被k整除。

因此，如果输入类似于arr = [5, 15, 6, 9] k = 7，则输出为True，因为我们可以取(5, 9)和(15, 6)这样的对。

为了解决这个问题，我们将遵循以下步骤：

  • n := 数组大小
  • 如果n是奇数，则
    • 返回False
  • occurrences := 一个空字典，如果某个键不存在，则返回0作为该缺失键的值
  • 对于i从0到n，执行以下操作：
    • 将occurrences[((array[i] mod k) + k) mod k]加1
  • 对于i从0到n，执行以下操作：
    • remainder := ((array[i] mod k) + k) mod k
    • 如果2 * remainder等于k，则
      • 如果occurrences[remainder]是奇数，则
        • 返回False
    • 否则，当remainder等于0时，则
      • 如果occurrences[remainder] AND 1不为零，则
        • 返回False
    • 否则，当occurrences[remainder]不等于occurrences[k - remainder]时，则
      • 返回False
  • 返回True

让我们看看下面的实现，以便更好地理解：

示例

在线演示

from collections import defaultdict
def solve(array, k):
   n = len(array)
   if n % 2 != 0:
      return False
   occurrences = defaultdict(lambda : 0)
   for i in range(0, n):
      occurrences[((array[i] % k) + k) % k] += 1
   for i in range(0, n):
      remainder = ((array[i] % k) + k) % k
      if (2 * remainder == k):
         if (occurrences[remainder] % 2 != 0):
            return False
      elif (remainder == 0):
         if (occurrences[remainder] & 1):
            return False
         elif (occurrences[remainder] != occurrences[k - remainder]):
            return False
   return True
arr = [5, 15, 6, 9]
k = 7
print(solve(arr, k))

输入

[5, 15, 6, 9], 7

输出

True

更新于：2020年12月30日

161 次浏览

开启您的职业生涯

完成课程获得认证

开始学习
广告