上面的方法确实比较“笨”，主要是体现在时间复杂度上。
如代码所示，需要执行(K^N)次increaseArray()的动作，而每次increaseArray()动作里面平均需要执行N/2次进位，
以及每次increaseArray()完毕之后需要执行isAvailableArray动作(平均包含N/2次比较)，以及getSummary动作(包含N次求和)
则总的时间复杂度为O(N*(K^N))
但是在此方法的基础上，我们其实是可以让它更快一点的。
此前的方法，可以等价为一个N位长度的K进制数的遍历和各个数位求和的问题。
其实，我们可以先找出一个"最小"的符合条件的K进制数a0，然后在此基础上直接找下一个(即第二小的)符合条件的K进制数a1，再在此基础上寻找a2,a3,...一直到找不到下一个进制数为止。
这里的"符合条件"指的是
1)各个数位之和=M
2)各个数位的内容介于min_value(在这里是1)以及max_value(在这里是K)
3)高位数字=M，然后再调整最后一个修改的高位，使得数位和=M。
这里可能有两种例外:N*min_value>M和N*max_valuea，意味着增加值的数位一定相比减少至的数位处于”更高位"。
于是，可以提出如下的算法：
在a=v[0]v[1]v[2]...v[N]，
找出最低位的"可以增加值"的数v[x]，
然后再在v[x+1]...v[N]中，找出最高位的"可以减少值"的数v[y]，
然后v[x]=v[x]+1,v[y]=v[y]-1。
这样构造出来的数自然满足和不变性和最小性原则
然后就是对"可以增加值"的v[x]以及可以减少值的v[y]的界定。
很显然，如果有下标x=2，则意味着v[x]可以加1。
再从d[x]开始向从前往后找第1个d[t]，使得d[x]+d[x+1]+...+d[t]>=2，则意味着v[t+1]可以减1。
然后来看一下大概的时间复杂度。为了找到一个解，我们需要经过N/2+N/4次的查找，所以总的时间与总的解的数量有关。
如果有A个解，则总的解复杂度为O(A*N)。
凭直觉，我觉得这种算法应该要快一点。
---------------------------------------------------------------------------
以下是大致代码
//获取第一个解(返回false表示没有找到。)
booleangetFirstAnswer(intary_value[],intary_size,intmin_value,intmax_value,inttarget_value){
for(inti=0;itarget_value){
returnfalse;
}elseif(sum_value==target_value){
returntrue;
}else{
for(inti=ary_size-1;i>=0;i--){
ary_value=max_value;
sum_value=sum_value+max_value-min_value;
if(sum_value>=target_value){
ary_value=ary_value-(sum_value-target_value);
returntrue;
}
}
returnfalse;
}
}
//计算各个元素与前一元素的差
voidcalcDifference(int[]ary_value,intary_size,int[]difference){
for(inti=ary_size-2;i>=0;i--){
difference=ary_value[i+1]-ary_value;
}
}
//查找最小的可以增加的元素编号，返回-1表示没有找到。
intgetMinIncreaseableIndex(int[]difference,intary_size){
intdiff=0;
for(inti=ary_size-2;i>=0;i++){
diff=diff+difference;
if(diff>=2){
returni;
}
}
return-1;
}
//在指定位置之后，查找最大的可以减少数字的位置编号。（-1表示没有找到，在本算法中，不可能出现该状况)
intgetMaxDecreaseableIndex(int[]difference,intary_size,intfirstIndex){
diff=0;
for(inti=firstIndex;i=2){
returndiff+1;
}
}
return-1;
}
//获取下一个"最小的"解,false表示没有找到有效解
booleangetNextAnswer(int[]ary_value,intary_size,int[]difference){
intfirstIndex=getMinIncreaseableIndex(difference,ary_size);
if(firstIndex=0)&&(firstIndex=0)&&(firstIndex-1=0)&&(lastIndex=0)&&(lastIndex-1
心目中的例子大致如下:(min=1,max=6,数字数量=7,目标值20)
FirstAnswer:
1111277
然后依次搜索到以下解
1111367
1111457
1111466
1111556
1112456
1112555
1113455
1114445
1123445
1124444
1133444
1223444
1233344
1333334
2233334
2333333 |
