在 Python 中查詢無法表示為給定陣列任意子集的和的最小正整數

假設我們有一個排序的正數陣列，該陣列按升序排序，我們需要找到無法表示為給定集合任意子集元素之和的最小正值。我們必須在 O(n) 時間內解決此問題。

因此，如果輸入類似於 A = [1, 4, 8, 12, 13, 17]，則輸出將為 2。

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

  • n := A 的大小

  • answer := 1

  • 對於 i 從 0 到 n，執行

    • 如果 A[i] <= answer，則

      • answer := answer + A[i]

    • 否則，

      • 退出迴圈

  • 返回 answer

示例

讓我們看看以下實現以獲得更好的理解 -

 即時演示

def get_smallest_element(A):
   n = len(A)
   answer = 1
   for i in range (0, n ):
      if A[i] <= answer:
         answer = answer + A[i]
      else:
         break
   return answer
A = [1, 4, 8, 12, 13, 17]
print(get_smallest_element(A))

輸入

[1, 4, 8, 12, 13, 17]

輸出

2

更新於: 2020年8月27日

516 次瀏覽

開啟你的 職業生涯

透過完成課程獲得認證

開始學習
廣告