查找无法用Python中给定数组的任何子集的和表示的最小正整数值
假设我们有一个正数的排序数组,该数组按升序排序,则必须找到不能表示为给定集合的任何子集的元素之和的最小正值。我们必须在O(n)时间内解决这个问题。
因此,如果输入类似于A=[1、4、8、12、13、17、17],那么输出将为2。
为了解决这个问题,我们将遵循以下步骤-
n:=A的大小
回答:=1
对于0到n范围内的i,执行
从循环中出来
答案:=答案+A[i]
如果A[i]<=答案,则
除此以外,
返回答案
示例
让我们看下面的实现以更好地理解-
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