在 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 次瀏覽

開啟你的職業生涯

完成課程獲得認證

開始學習
廣告