0357. Count Numbers with Unique Digits¶
题目信息¶
- 题号:
0357
- 难度:
Medium
- 主题:
十进制数字、计数、组合、边界
- 原题:
- 重点:
统计范围为
0 <= x < 10^n、数字表示中各位互不相同、前导零不属于表示、n=0只包含数字 0
题目重述¶
给定整数 n,统计所有满足 0 <= x < 10^n,且十进制表示中没有任何重复数字的整数数量。整数的通常十进制表示不包含前导零,因此例如 7 只包含一位数字,而不是被视为 007。
n 位于 [0, 8]。数字 0 本身符合条件;当 n=0 时,范围为 [0,1),答案为 1。题目返回计数,不需要列出这些整数。
自建示例¶
只考察一位数:
输入:n = 1
输出:10
解释:范围是 0 到 9,每个数的十进制表示最多只有一位,不可能出现重复数字。
三位范围:
输入:n = 3
输出:739
解释:答案包含 0、一位数、两位数和三位数;每个整数都按不带前导零的正常表示检查数字是否重复。
按实际位数计数,首位与后续位分开¶
范围 0 <= x < 10^n 包含位数从 0 到 n 的所有非负整数。数字 0 单独贡献一种空范围意义上的计数;对于长度至少 1 的普通十进制表示,首位不能为 0,所以有 9 种选择,之后每增加一位,可用数字数依次为 9、8、7……。
例如长度为 3 的数字有 9 * 9 * 8 种:第一位从 1 到 9,第二位可以选剩余的 9 个数字,第三位再从剩余 8 个数字中选。把各个长度的计数累加即可;题目范围最多 8 位,不会遇到十进制数字耗尽的问题。
C++ 实现¶
class Solution {
public:
int countNumbersWithUniqueDigits(int n) {
n = std::min(n, 10);
int result = 1; // 数字 0
int ways = 1;
int available = 9;
for (int length = 1; length <= n; ++length) {
ways *= (length == 1 ? 9 : available);
result += ways;
if (length > 1) --available;
}
return result;
}
};
代码分析¶
ways 表示当前位数的完整计数,首位使用 9 个非零数字,后续位从未使用数字中选择;结果初始的 1 覆盖数字 0 和 n == 0。循环长度最多 10,时间和额外空间均为 O(min(n, 10))。