檢查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 次瀏覽

開啟您的職業生涯

完成課程獲得認證

開始學習
廣告