正数数组的最小不可组成和
题目
给定一个正数数组arr,其中所有的值都是整数,以下是最小不可组成和的概念:把arr每个子集内的所有元素加起来会出现很多值,其中最小的记为min,最大的记为max。在区间[min, max]上,如果有数不可以被arr某一个子集相加得到,那么其中最小的那个数就是arr的最小不可组成和。在区间[min, max]上,如果所有的数都可以被arr的某一个子集相加得到,那么max + 1是arr的最小不可组成和。
进阶题目
如果已知正数数组arr中肯定有1这个数,是否能更快地得到最小不可组成和
原问题:使用动态规划。arr中所有数的相加和sum即是该数组的最大累加和,所有arr子集的累加和必然在[0, sum]区间上。生成长度为sum+1的dp数组,dp[i] == True表示i这个累加和可以被arr的子集相加得到,否则不能。如果arr[0…i]这个范围上的数组成的子集可以累加出k,那么arr[0…i+1]这个范围上的数组成的子集中必然可以累加出k + arr[i+1]。时间复杂度O(N*sum),空间复杂度O(sum)
def unformedSum1(arr):
import sys
if arr == None or len(arr) == 0:
return 1
sumMax = 0
sumMin = sys.maxsize
for i in range(len(arr)):
sumMin = min(sumMin,arr[i])
sumMax += arr[i]
dp = [False for i in range(sumMax+1)]
dp[0] = True
for i in range(len(arr)):
for j in range(sumMax,arr[i]-1,-1):
if dp[j-arr[i]]:
dp[j] = True
for i in range(sumMin,len(dp)):
if not dp[i]:
return i
return sumMax + 1
进阶问题:具体过程如下:将arr进行排序,排序后必然有arr[0] == 1。从左往右计算每个位置i的range。range表示当计算到位置arr[i]时,[1, range]上所有的数都可以被arr[0…i-1]的某一个子集累加出来。初始时range = 0。如果arr[i] > range+1。说明在arr[0…i]上,range+1这个数一定不能累加出来。此时返回range + 1即可。如果arr[i]≤range+1arr[i]≤range+1,说明[1,range+arr[i]]区间上所有的正数都可以被arr[0…i]上的某一个子集累加出来,所以令range += arr[i],然后继续计算下一个位置。时间复杂度O(NlogN),空间复杂度O(1)。
def unformedSum2(arr):
if arr == None or len(arr) == 0:
return 1
arr.sort()
range_ = 0
for i in range(len(arr)):
if arr[i] <= range_ + 1:
range_ += 1
else:
break
return range_+1