在 Python 中查找将数组分成两个乘积相等的子数组的元素

假设我们有一个大小为 N 的数组；我们必须找到一个元素，它将数组分成两个乘积相等的子数组。如果不存在这样的划分，则返回 -1。

因此，如果输入类似于 [2,5,3,2,5]，则输出将为 3，子数组为：{2, 5} 和 {2, 5}

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

  • n := 数组大小
  • multiply_pref := 一个新列表
  • 将 array[0] 插入 multiply_pref 的末尾
  • 对于 i 从 1 到 n，执行以下操作：
    • 将 multiply_pref[i-1]*array[i] 插入 multiply_pref 的末尾
  • multiply_suff := 一个大小为 n 的列表，并填充为 None
  • multiply_suff[n-1] := array[n-1]
  • 对于 i 从 n-2 到 -1，递减 1，执行以下操作：
    • multiply_suff[i] := multiply_suff[i+1]*array[i]
  • 对于 i 从 1 到 n-1，执行以下操作：
    • 如果 multiply_pref[i] 与 multiply_suff[i] 相同，则
      • 返回 array[i]
  • 返回 -1

示例代码

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

在线演示

def search_elem(array):
   n = len(array)
   multiply_pref = []
   multiply_pref.append(array[0])
   for i in range(1, n):
      multiply_pref.append(multiply_pref[i-1]*array[i])
   multiply_suff = [None for i in range(0, n)]
   multiply_suff[n-1] = array[n-1]
   for i in range(n-2, -1, -1):
      multiply_suff[i] = multiply_suff[i+1]*array[i]
   for i in range(1, n-1):
      if multiply_pref[i] == multiply_suff[i]:
         return array[i]
   return -1
array = [2,5,3,2,5]
print(search_elem(array))

输入

[2,5,3,2,5]

输出

3

更新于：2020年8月28日

105 次浏览

开启你的职业生涯

完成课程获得认证

开始学习
广告