首页 > 代码库 > [算法]请用A中元素组成一个大于k的最小正整数
[算法]请用A中元素组成一个大于k的最小正整数
给定A[]={0,1,3,8},A是U={0，1，2，3，4，5，6，7，8，9}的子集，k是正整数，请用A中的元素组成一个大于k的最小正整数。
思路：
1、使用flag数组标记A中的元素，
bool flag[10];
顺便记录A中的最小元素
bool flag[10] = {0,0,0,0,0,0,0,0,0,0};int min = 10;for(int i = 0; i < n; ++i){ flag[a[i]] = true; min = min < a[i] ? min : a[i];}
2、使用bound数组表示：bound[i]表示比i大，且在A中的最小元素，倘若在A中找不到比i大的元素，则令bound[i]=10
如A={0,1,3,8}对应的bound[] = {1,3,8,8,8,8,8,8,8,10,10};
int bound[10];for(int i = 0, j; i < 10; ++i){ for(j = i; j < 10 && !flag[j]; ++j); if(j == i){ for(j = i+1; j < 10 && !flag[j]; ++j); } bound[i] = j;}
3、将k转换为数组num表示，length记录数组长度
int num[maxSize];int j = maxSize;num[--j] = k % 10;k /= 10;while(k){ num[--j] = k % 10; k /= 10;}int i = 0;while(j < maxSize){ num[i++] = num[j++];}int length = i;
4、从k的最高位向最低位遍历，即从数组num从头遍历，result[]记录所求的最小正整数各位
4.1若num[i]在A中，即flag[num[i]]为真，
若num[i]不是k的个位数上的数字，将num[i]写入result，
若num[i]是k的个位数上的数字，
若bound[num[i]] < 10，将bound[num[i]]写入result
否则转向4.3
否则转4.2
4.2若bound[num[i]] < 10，即A中有比num[i]大的数，bound[num[i]]写入result，然后将result的剩余位数全部置为min。
4.3若bound[num[i]] =10,即A中没有比num[i]大的数，即返回修改result，转向4.4
4.4从当前位置往k的高位数遍历，即从当前位置num[i] 往 num[0]遍历，找出使用bound[num[i]] < 10成立的bound[num[i]]，然后修改result，并并将后续的改为min；倘若bound[num[i]] < 10一直不成立，则表示大于k的最小正整数的位数比k多一位，将最高的两位置为A能表示的最小的两位数，剩下的使用min充填即可。
int result[maxSize],len; for(int i = 0; i < length; ++i){ if(flag[num[i]]){ if(i != length-1){ result[i] = num[i]; } else{ if(bound[num[i]] < 10){ result[i] = bound[num[i]]; len = length; } else{ len = fill_rest(bound,result,num, length,i,min); } } } else{ if(bound[num[i]] < 10){ result[i] = bound[num[i]]; while(++i < length){ result[i] = min; } len = length; } else{ len = fill_rest(bound,result,num, length,i,min); } break; } }
int fill_rest(int* bound, int* result, int* num, int length, int i, int min){ while(--i >= 0 && bound[num[i]] == 10); if(i >= 0){ result[i] = bound[num[i]]; while(++i < length){ result[i] = min; } return length; } else{ if(min){ result[++i] = min; } else{ result[++i] = bound[min]; } while( ++i <= length){ result[i] = min; } return length+1; }}
最后将result转为正整数返回
int sum = 0;for(int i = 0; i < len; ++i){ sum *= 10; sum += result[i];}return sum;
参考文献
http://www.cnblogs.com/chonghui1001/archive/2011/09/25/2190394.html
本文基于知识共享署名-非商业性使用 3.0 许可协议进行许可。欢迎转载、演绎，但是必须保留本文的署名林羽飞扬,若需咨询，请给我发信