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

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

程序员文章站 2024-02-03 11:12:40
...

题目

给定一个正整数数组arr,其中所有的值都为整数,以下是最小不接组成和的概念

  • 把arr每个子集的所有元素加起来出现很多值,其中最小的记为min,最大的记为max
  • 在区间[min,max]上,如果有数不可以被arr某个子集相加得到,那么其中最小的那个数就是最小不可组成和。
  • 如果[min,max]所有的数都可以相加得到,那么max+1就是arr的最小不可组成和

举例

arr=[1,2,3,4],返回11
arr=[2,3,4] 返回7

解答

暴力搜索

  • 收集每一个子集的累加和,存到一个hash表中,然后从min值开始递增查找,哪个正数不再hash表中,即返回该数即可
public int baoli(int[]arr){
    if(arr==null||arr.length==0)
        return 1;
    HashSet<Integer> set=new HashSet<>();
    process(arr,0,0,set);
    int min=Integer.MAX_VALUE;
    for(int i=0;i!=arr.length;i++){
        min=Math.min(min,arr[i]);
    }
    for(int i=min+1;i!=Integer.MAX_VALUE ;i++){
        if(!set.contains(i))
            return i;
    }
    return 0;
}
public void process(int[]arr,int i,int sum;HashSet <Integer>set){
if(i==arr.length){
    set.add(sum);
    return ;
}
    process(arr,i+1,sum,set);//不包含当前数arr[i]
    process(arr,i+1,sum+arr[i],set);//包含当前数
}

分析

  • 子集的个数为2^N,时间复杂度为O(2^N),收集子集和的过程,递归函数process最多有N层,空间复杂度O(N)

动态规划

思路分析

  • 假设arr所有数累加和为sum,那么arr子集的累加和必定在[0,sum]区间内,可以申请空间sum+1的boolean型数组dp[],dp[i]如果为true,那么表示i可以被arr的子集相加得到,
  • 如果arr[0…i]这个范围的数组成的子集可以累加出k,那么arr[0…i+1]组成的子集必然也可以累加出k+arr[i+1]

代码

public int dymicp(int[]arr){
    if(arr==null||arr.length==0)
        reeturn 1;
    int sum=0,min=Math.MAX_VALUE;
    for(int i=0;i<arr.length;i++)
    {
        sum+=arr[i];
        min=Math.min(arr[i],min);
    }
    boolean[] dp=new boolean[sum+1];
    dp[0]=true;
    for(int i=0;i!=arr.length;i++){
        for(int j=sum;j>=arr[i];j--){
            dp[j]=dp[j-arr[i]]?true:dp[j];
        }
    }
    for(int i=min;i!=dp.length;i++){
        if(!dp[i])
            return i;
    }
    return sum+1;

}

复杂度

  • 时间复杂度:0~sum的累加和都要看是否能被夹出来,所以每次更新的时间复杂度都是O(sum),子集和状态从arr[0]的范围增加到arr[0…N-1],所以更新的次数为N,总体的时间复杂度为O(N*sum)
  • 空间复杂度为:O(N)

特殊情况,正数数组中含有1

分析

  1. 将arr排序,必然有arr[0]=1;
  2. 从左往右计算每个位置i上的range(0<=i<=N).range代表计算到arr[i]时,[1,range]区间内得所有正数都可以被arr[0…i-1]的某个子集相加表示,初始时arr[0],range=0;
  3. 如果arr[i]>range+1,因为arr是有序的,所以arr[i]往后的数都不是出现range+1,直接返回;如果arr[i]<=range+1,说明[1,range+arr[i]]区间内的所有整数都可以被arr[0,…i-1]的某个子集表示,这是因为区间[1,range],可以由[0..i-1]子集和表示,对于k>range,的数,k-arr[i]

实现

public int fin(int []arr){
    if(arr==null||arr.length==0)
        return 1;
    Arrays.sort(arr);
    int range=0
    for(int i=0;i<arr.length;i++){
        if(arr[i]>range+1)
            return range+1;
        else
            range+=arr[i];
    }
    return range+1;
}