LeetCode 357. 统计各位数字都不同的数字个数
题目描述
题意分析
统计
0 <= x < 10^n中十进制各位数字互不重复的整数数量。看的是整数本身的实际位数，不能用前导零把较短的数补成n位；0 也要计入答案。
解法：排列计数
核心思路
[!blue]
不必枚举区间中的每个整数，可以按实际位数分别计数。不同位数的整数不会重复，最后把它们的数量相加即可。
对一个多位数，首位只能从 1 到 9 中选，有 9 种选择。首位确定后，第二位可以使用 0，但不能重复首位，因此仍有 9 种；第三位排除已经用过的两种数字，剩 8 种。每增加一位，可选数字就减少一种，用乘法原理得到该位数的合法数量。
unique保存当前位数的合法正整数数量，初始为单个非零数字的 9 种；available保存下一位可选的数字数量，初始也为 9。每轮先用unique *= available得到更长一位的数量，再加入total，最后把available减一，为下一轮做准备。当
n >= 1时，total从 0 到 9 的 10 个整数开始，因此 0 只计入一次。n == 0时范围为[0, 1)，只有 0，单独返回 1。十种数字用完后也不能再扩展互不重复的数。
解题步骤
n == 0时返回 1。- 初始化
total = 10、unique = 9、available = 9。- 从两位数开始，乘上当前可用数字数，把该位数的合法数量加入总数，再减少下一位的可选数量。
- 位数达到
n或可用数字耗尽时结束，返回total。
代码实现
class Solution {
public int countNumbersWithUniqueDigits(int n) {
if (n == 0) {
return 1;
}
// 总数含零，单个非零首位则只有九种
int total = 10;
int unique = 9;
int available = 9;
for (int i = 2; i <= n && available > 0; i++) {
// 先扩展本位并累计，再减少下一位可选数量
unique *= available;
total += unique;
available--;
}
return total;
}
}
func countNumbersWithUniqueDigits(n int) int {
if n == 0 {
return 1
}
// 总数含零，单个非零首位则只有九种
total := 10
unique := 9
available := 9
for i := 2; i <= n && available > 0; i++ {
// 先扩展本位并累计，再减少下一位可选数量
unique *= available
total += unique
available--
}
return total
}
复杂度分析
- 时间复杂度：$O(n+1)$，在题目位数范围内逐位累积。
- 空间复杂度：$O(1)$，滚动乘积与总数。
关键点总结
[!green]
- 首位不能零，但后续位可以选尚未用过的零。
- 数字出现的位置有意义，应计算排列数量，不能只计算选了哪些数字。
- 按实际位数分组既覆盖整个范围，也避免前导零造成重复计数。
易错点总结
[!yellow]
- 单个非零位初值设成十，会重复计入前导零形式。
- 乘法前先减少选择数，会少算第二位的九种选择。
- 先加入旧乘积再更新，会重复计算前一种位数。
n == 0并非没有合法数，区间里仍包含 0。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 1012. 至少有 1 位重复的数字 | 困难 | 统计至少有重复数码的整数可用总数减去无重复数码的数量，数位选择模型互补。 |
| 902. 最大为 N 的数字组合 | 困难 | 同样按数位统计而不逐个枚举，原题限制可用数码集合，本题限制一个数内不能重复。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！