在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 次浏览

开启你的职业生涯

完成课程获得认证

开始学习
广告