正数数组的最小不可组成和
程序员文章站
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
分析
- 将arr排序,必然有arr[0]=1;
- 从左往右计算每个位置i上的range(0<=i<=N).range代表计算到arr[i]时,[1,range]区间内得所有正数都可以被arr[0…i-1]的某个子集相加表示,初始时arr[0],range=0;
- 如果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;
}