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

开启你的 职业生涯

通过完成课程获得认证

开始学习
广告