题目
在十进制中，任意一个正整数都可以用字符 ‘0’ - ‘9’ 表示出来，但是当 ‘0’ - ‘9’ 这些字符每种字符的数量有限时，可能有些正整数就无法表示出来了，比如你有两个 ‘1’，一个 ‘2’，那么你能表示出来 11, 12, 121 等等，但是无法表示出 10,122,200 等数。
现在你手上拥有一些字符，它们都是 ‘0’ - ‘9’ 的字符，你可以选出其中一些字符然后将它们组合成一个数字，那么你无法组成的最小正整数是多少？
输入
第一行包含一个由字符 '0' - '9' 组成的字符串，表示可以使用的字符。
1 ≤ 字符串长度 ≤ 1000
样例输入
55
样例输出
1
Hint
Input Sample 2
123456789
Output Sampe 2
10
思路
- 题目要求的是无法组成的最小正整数，所以如果给定的字符没有完全包含 ‘1’ - ‘9’ 则应返回第一个没有包含的数。
- 如果出现次数最小的数是 0 ，则返回 \(10^n\), n 为 0 出现的次数 + 1
- 如果出现次数最小数非 0 或者次数等于 0 的次数 ,则返回只有该数组成的数，个数未该数的个数 + 1
实现
/**
* str 全为 '0'-'9' 的字符，求其不能组成的最小正整数
* 如：str 为 1123456789 则不能组成的最小正整数为 10
*
* @param str 由多个 '0'-'9' 的字符组成
* @return 不能组成的最小正整数
*/
public String minIntegral(String str) {
StringBuilder builder = new StringBuilder();
int[] nums = new int[10];
//统计每个字符出现的次数
for (int i = 0; i < str.length(); i++) {
nums[str.charAt(i) - '0'] += 1;
}
//找到 '1'-'9' 中第一个出现最少的数字及次数
int leastNum = 0, leastCount = Integer.MAX_VALUE;
for (int i = 1; i < nums.length; i++) {
if (leastCount > nums[i]) {
leastCount = nums[i];
leastNum = i;
}
}
//如果一次没有出现，则最小数为没有出现的字符
if (leastCount == 0) {
builder.append(leastNum);
} else {
//'0' 的个数是最少的，则相应的最少数为 100..
// 比如 '0' 只出现了 2 次，而其它数字出现均多余 2 次，则最小数为 100
if (nums[0] < leastCount) {
builder.append("1");
for (int i = 0; i <= leastCount; i++) {
builder.append("0");
}
//非 '0' 数出现次数最少，则相应的最小数为将该数全部取出组成的数字
} else {
for (int i = 0; i <= leastCount; i++) {
builder.append(leastNum);
}
}
}
return builder.toString();
}