组合问题

Question

题目如下：
给定一个集合A=[0,1,3,8](该集合中的元素都是在0，9之间的数字，但未必全部包含)，指定任意一个正整数K，请用A中的元素组成一个大于K的最小正整数。 
* 比如，A=[1,0] K=21 那么输出结构应该为100 
我只能做出K为固定位数时的情况，当K的位数不定是，我想了很久也不知道怎么解决，请各位指点指点，谢谢！

Answer 1

public static void main(String[] args)
    {
        int[] a = new int[]{8,2,0};
        int k = 108000;
        Arrays.sort(a);//对数组a进行排序。
        String s = String.valueOf(k);//转换String来求K的长度。
        int[] b = new int[s.length()];//new一个跟K长度一样的数组。
        StringBuffer sb = new StringBuffer();//取得符合数放入sb中，进行连接起来。
        for (int i = 0; i < s.length(); i++) {//把K这个数放入数组b中
            b[i] = (int) (k / Math.pow(10, i)) % 10;
        }
        int count = 0;//计数用，K有多少位就生成多少位的数
        boolean flag = false;
        for (int i = b.length - 1; i >= 0; i--) {
            for (int j = 0; j < a.length; j++) {
                if (b[i] == a[j] && count < s.length() - 1) {
                    sb.append(a[j]);
                    count++;
                    break;
                } else if (a[j] > b[i]) {
                    sb.append(a[j]);
                    count++;
                    flag = true;
                    break;
                }
            }
            if (flag) {
                break;
            }
        }
        for (int i = 0; i < s.length() - count; i++) {//位数不够的话，进行补位。
            sb.append(a[0]);
        }
        System.out.println(sb);
    }不知道是否有bug.自己测试通过了。

Answer 2

楼上的算法不对.
int[] a = new int[]{8,2,0};
int k = 109000;
程序append不上.这道题是典型的贪心算法,
分两种情况讨论:1)所求的数的位数与K的位数相同
从左到右至少有一位比K对应的所在位的数字大,比它高位的和K对应位的数字相等.
所以从最高位向右开始扫描:
1-1 从A取数,能相等就使其相等,不能相等分两种情况:
   1-1-1: 所有A里的值都小于K对应位:向左一位一位回朔,使高位大于K对应位,该高位的右边低位都补充A的最小数,得到答案.
   1-1-2: A里有数字大于K对应位,取符合条件的最小数,右边低位补充A中最小数,得到答案.
1-2 如果到最右到最低位都相等,或者向左最高位回朔(1-1-1)都无法大于K跳到2)2)所求的数的位数为K的位数+1
最高位放不是0的最小数,其余位放A的最小数.

Answer 3

请问一下哪里不对？我不知道程序你跑了没有。
“所求的数的位数与K的位数相同 ”
你说的这一点我已经用Arrays.sort(a);//对数组a进行排序。程序没看明白就唧唧歪歪。
你只会空谈，怎么不把程序贴出来秀秀呀。

Answer 4

谢谢，我学习了。public class NumZuHe { /**
 * @param args
 */
private int count;
private static int[] array=new int[]{1,5,2,3,5,6,8};
private int[] array2;//把所要比较的数字放进此数组里
public static void main(String[] args) {
// TODO Auto-generated method stub
NumZuHe n=new NumZuHe();
System.out.print(n.method(array,888));
}

//数组排序，把小的数字排在最前面
public void swap(int[] array){
for(int i=0;i<array.length-1;i++){
for(int j = i+1;j<array.length;j++){
if(array[i]>array[j]){
int temp=array[i];
array[i]=array[j];
array[j]=temp;
}
}
}
}


public int method(int[] array,int K){
swap(array);//排序
String s=String.valueOf(K);//数字换成字符串
array2=new int[s.length()];
for(int i=s.length()-1;i>=0;i--){
array2[i]=(int)(K/Math.pow(10,i))%10;//把K放进数组里，低位数字放在前面
}
StringBuffer sbf=new StringBuffer();
boolean flag=false;
for(int i=array2.length-1;i>=0;i--){//从最高位开始遍历K的每位数字
for(int j=0;j<array.length;j++){//从最小的数字开始遍历原数组的每个数字
if(array[array.length-1]<=array2[array2.length-1]){
//如果原数组的最大那个数字比K的最高位小，则所求的数要比K多一位，
//最高位为非0的最小数,其他位为数组的最小的数
flag=true;   
if(array[0]==0){
sbf.append(array[1]);
}
else sbf.append(array[0]);
break;
}
if(array[j]==array2[i]&&count<array2.length){
//如果找到相等的数，则把它添加，再看下一位
sbf.append(array[j]);
count++;
break;
}
else if(array[j]>array2[i]&&count<array2.length){
//如果K的某位比某数小（记得原数组是从小到大遍历的），
//则添加该数，K的低位就不用再比了,直接添加最小的数
sbf.append(array[j]);
count++;
flag=true;
break;
}

}
if(flag) break;

}
for(int k=count;k<array2.length;k++){
sbf.append(array[0]);
}
return Integer.parseInt(sbf.toString());
}}

Answer 5

public class ZuHe4 { /**
 * @param args
 */
int count,index;
public static int K=888;
public static void main(String[] args) {
// TODO Auto-generated method stub
ZuHe4 z=new ZuHe4();
int[]array=new int[]{1,2,3,8,5};
System.out.println(z.method(array, K));
}

public void swap(int[] array){
for(int i=0;i<array.length-1;i++){
for(int j=i+1;j<array.length;j++){
if(array[j]<array[i]){
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
}
}

public int getNum(int[] array,int num){
for(int i=0;i<array.length;i++){
if(array[i]>num){
return array[i];
}
}
return -1;
}

public int traversalToLeft(int[] array,int ,int num){
if(<0) return count;
if(array[]>=num){
count++;
traversalToLeft(array,-1,num);
}
return count;
}

public int method(int[] array,int K){
swap(array);
String s=String.valueOf(K);
String str=""+array[array.length-1]+1;
boolean flag=false;
StringBuffer sbf=new StringBuffer();
int[] array2=new int[s.length()];
for(int i=0;i<s.length();i++){
array2[i]=(int)(K/Math.pow(10, s.length()-i-1))%10;
}
for(int i=0;i<array2.length;i++){
for(int j=0;j<array.length;j++){
if(array2[i]==array[j]){
sbf.append(array[j]);
break;
}
if(array2[i]<array[j]){
sbf.append(array[j]);
index=i;
flag=true;
break;
}
if(i==array2.length-1&&array2[i]==array[array.length-1]){
sbf.append(array[array.length-1]);
traversalToLeft(array2,i,array[array.length-1]);
sbf.setLength(sbf.length()-count);
index=i-count;
if(sbf.length()>0){
str=sbf.substring(i-count, i-count+1);
}
int n=getNum(array,Integer.parseInt(str));
if(sbf.length()>0){
sbf.setLength(sbf.length()-1);
}
if(n==-1){
sbf.append(array[0]==0?array[1]:array[0]);
}
else sbf.append(n);
flag=true;
break;
}
if(array2[i]>array[array.length-1]){
traversalToLeft(array2,i,array[array.length-1]);
index=i-count;
if(sbf.length()>0){
str=sbf.substring(index>0?index:0, index+1>1?index:1);
}
sbf.setLength(sbf.length()-count>0?sbf.length()-count:0);
int m=getNum(array,Integer.parseInt(str));
if(m==-1){
sbf.append(array[0]==0?array[1]:array[0]);
}
else {
sbf.append(m);
}
flag=true;
break;
}
}
if(flag){
break;
}
}
for(int i=index+1;i<array2.length;i++){
sbf.append(array[0]);
}
return Integer.parseInt(sbf.toString());
}}