欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

正数数组的最小不可组成和

程序员文章站 2024-02-03 13:54:28
...

题目

  给定一个正数数组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