在Python中查詢一個整數X，它是陣列中除一個元素之外所有元素的約數

假設我們有一個數字陣列；我們必須找到一個數字B，它是給定陣列中除一個元素之外所有元素的約數。我們必須記住所有元素的最大公約數不是1。

因此，如果輸入類似於{8, 16, 4, 24}，則輸出將為8，因為它是除4之外所有元素的約數。

為了解決這個問題，我們將遵循以下步驟：

  • n := 陣列大小
  • 如果n等於1，則
    • 返回(array[0] + 1)
  • prefix := 一個大小為n的陣列，並填充為0
  • suffix := 一個大小為n的陣列，並填充為0
  • prefix[0] := array[0]
  • 對於i從1到n，執行
    • prefix[i] := (array[i] 和 prefix[i - 1]) 的最大公約數
  • suffix[n - 1] := array[n - 1]
  • 對於i從n - 2到-1，遞減1，執行
    • suffix[i] := (suffix[i + 1] 和 array[i]) 的最大公約數
  • 對於i從0到n + 1，執行
    • cur := 0
    • 如果i等於0，則
      • cur := suffix[i + 1]
    • 否則，如果i等於n - 1，則
      • cur := prefix[i - 1]
    • 否則，
      • cur := (prefix[i - 1] 和 suffix[i + 1]) 的最大公約數
    • 如果 array[i] mod cur 不等於 0，則
      • 返回 cur
  • 返回 0

示例程式碼

讓我們看看下面的實現以更好地理解：

from math import gcd
def getDivisor(array):
   n = len(array)
   if (n == 1):
      return (array[0] + 1)
   prefix = [0] * n
   suffix = [0] * n
   prefix[0] = array[0]
   for i in range(1, n):
      prefix[i] = gcd(array[i], prefix[i - 1])
   suffix[n - 1] = array[n - 1]
   for i in range(n - 2, -1, -1):
      suffix[i] = gcd(suffix[i + 1], array[i])
   for i in range(0, n + 1):
      cur = 0
      if (i == 0):
         cur = suffix[i + 1]
      elif (i == n - 1):
         cur = prefix[i - 1]
      else:
         cur = gcd(prefix[i - 1], suffix[i + 1])
      if (array[i] % cur != 0):
         return cur
   return 0;
array = [8, 16, 4, 24]
print(getDivisor(array))

輸入

[8, 16, 4, 24]

輸出

8

更新於：2020年8月28日

96 次瀏覽

開啟你的職業生涯

完成課程獲得認證

開始學習
廣告