【Java】PAT Basic Level 1023 组个最小数

题目 1024 组个最小数

作者 CAO, Peng

单位 Google

给定数字 0-9 各若干个。你可以以任意顺序排列这些数字，但必须全部使用。目标是使得最后得到的数尽可能小（注意 0 不能做首位）。例如：给定两个 0，两个 1，三个 5，一个 8，我们得到的最小的数就是 10015558。

现给定数字，请编写程序输出能够组成的最小的数。

输入格式：

输入在一行中给出 10 个非负整数，顺序表示我们拥有数字 0、数字 1、……数字 9 的个数。整数间用一个空格分隔。10 个数字的总个数不超过 50，且至少拥有 1 个非 0 的数字。

输出格式：

在一行中输出能够组成的最小的数。

输入样例：

2 2 0 0 0 3 0 0 1 0

输出样例：

10015558

---

思路

题目输入的信息是0-9这十个数字的个数，而最终却要以一定顺序输出所有的0-9数字，于是我的思路是把输入的信息转换为一个字符数组arr，用来存储所有可用的数字。比如给定数字0的个数为2，数字1的个数为3，那么字符数组的0-4号字符就是 0 0 1 1 1 。

接下来只要按照角标升序遍历这个字符数组，输出每一个字符，就可以了。有一个问题就是，数字0不能作为首位，因此如果给定的数字0的个数>0的话，就要找到最小的非零数字来作为首位。这个很好解决，用一个变量 t 来存储题目给定的数字0的个数，那么这个 t 就是字符数组中应当输出的首个字符的角标。比如，给定数字0的个数为3，那么t的值为3，则arr[3]存储的就是最小的非零数字字符。如果题目给定的数字0的个数为0，那么就应该从角标0开始输出字符，也就是t=0。之后再遍历字符数组，依次输出每个字符，注意要跳过角标为 t 的那个字符，因为它已经输出过一遍了。

---

Java代码

/*
功能：给定指定个数的0-9十个数字，把它们全用上，组成一个最小的数字并返回。
*/
import java.io.*;
class Main{
    public static void main(String[] args) throws IOException{
        //接收输入
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] s = br.readLine().split(" +");    //读取输入并以空格为间隔切分为字符串数组
        //String[] s = {"0","0","0","3","0","0","0","2","0","0"};
 
        //根据输入，生成升序字符数组
        char[] arr = new char[100];
        for(int i=0,k=0;i<10;i++){    //k是字符数组的角标，i表示当前数字，也就是0-9的第几个数字
            int t = Integer.parseInt(s[i]);    //当前数字的个数t
            for(int j=0;j//把指定个数的当前数字i存入字符数组
                arr[k] = (char)(i + '0');
                k++;
            }
        }
 
        //输出
        int t=Integer.parseInt(s[0]);        //第一个输出的字符角标，即最小的非零数字字符所在角标
        System.out.print(arr[t]);            //先把角标为t的字符串输出
        for(int i=0;i//遍历字符数组，依次输出字符
            if(i==t)        //把角标为t的字符跳过去
                continue;
            System.out.print(arr[i]);
        }
 
    }// void main 
}// class Main