LeetCode 357. 统计各位数字都不同的数字个数

2025-05-30 HGNULB 约 8 分钟

文章信息 7 个分类 3 个标签

分类

题目描述

✅ 357. 统计各位数字都不同的数字个数

题意分析

统计满足 $0 \le x < 10^n$ 且各位数字互不相同的整数 x 的个数。注意区间是左闭右开，且包含 0。

$x < 10^n$ 等价于「x 的十进制位数不超过 n」，所以问题可以按位数分层：分别数出 1 位数、2 位数、……、n 位数中各位互异的有多少，再加上 0 这一个。

「各位互不相同」是排列型约束——写下一位后，这个数字就从后续可选集合中永久移除。这类「选了就不能再选、且顺序有意义」的条件天然对应排列数公式，而不是组合数。

关键约束是 0 <= n <= 8。上界只有 8，不是巧合：十进制只有 10 个数字，位数一旦超过 10 就必然出现重复，所以 n 再大答案也不会增长；而 n = 8 时答案约为 189 万，仍在 int 范围内。这条约束说明本题根本不需要大数或取模，直接累乘即可。

边界包括：n = 0 时区间是 $[0, 1)$，只有 0 一个数，答案为 1；n = 1 时是 0 到 9 共 10 个，全部互异，答案为 10；以及位数超过 10 后可选数字耗尽的情形（本题受 n <= 8 保护，但写代码时留一道防线更稳）。

解法：排列计数

核心思路

暴力做法是从 0 枚举到 $10^n - 1$，逐个把每个数拆位判重。在 n = 8 时要检查 1 亿个数，每个还要做位分解，明显浪费——因为满足条件的只有不到 200 万个，绝大多数枚举都以失败告终。

换成构造式计数：不去检验现成的数，而是直接数「能造出多少个」。按位数 k 分层，考察恰好 k 位且各位互异的数有多少个。

首位不能是 0（否则就不是 k 位数了），所以有 9 种选择：1 到 9。第二位可以是 0，但不能与首位相同，所以在 10 个数字里去掉已用的 1 个，剩 9 种。第三位要去掉已用的 2 个，剩 8 种。以此类推，第 j 位（从 1 计）的可选数量是 10 - (j - 1)，唯独首位因为不能取 0 而额外少 1。

于是恰好 k 位的互异数个数为 $f(k) = 9 \times 9 \times 8 \times \cdots \times (11 - k)$，共 k 个因子。这里 $f(1) = 9$（1 到 9），加上 0 这一个特殊值，1 位以内共 10 个。

最终答案是 $1 + \sum_{k=1}^{n} f(k)$，其中的 1 来自数字 0。

代码把这个求和写成迭代递推，维护三个量：total 是已累计的答案；unique 是当前位数下恰好 k 位的互异数个数，即 $f(k)$；available 是「下一位还剩多少个数字可选」。

不变量是：每轮循环开始时，unique 等于 $f(i-1)$，available 等于计算 $f(i)$ 时新增那一位的可选数量，total 等于位数不超过 i-1 的答案。循环体执行 unique *= available 完成从 $f(i-1)$ 到 $f(i)$ 的递推，再把它累加进 total，最后 available-- 为下一轮做准备。

初值的设置对应「已经处理完 1 位数」这一状态：total = 10（0 到 9 全部合法），unique = 9（即 $f(1)$），available = 9（第二位可选 10 个数字减去首位已用的 1 个）。循环从 i = 2 起步，正好接上。

解题步骤

先特判 n == 0 返回 1。之所以要单独处理，是因为后续的初值 total = 10 预设了「1 位数已计入」，而 n = 0 时连 1 位数都不该计，只有 0 本身合法。

令 total = 10、unique = 9、available = 9。之所以 total 起步是 10 而不是 9，是因为它已经把数字 0 算进去了（0 到 9 共 10 个）；而 unique 只统计「恰好 1 位且首位非 0」的 9 个，两者语义不同，不能混用。

循环从 i = 2 递增到 n。之所以从 2 开始，是因为 1 位数的贡献已经写进初值，从 2 开始才不会重复计入。

循环条件里额外加 available > 0。之所以要这道防线，是因为当位数增长到 11 时可选数字会耗尽，available 变成 0 甚至负数，继续乘会把 unique 归零或变成负数；虽然 n <= 8 保证不会触发，但这一条让递推在数学上自洽。

每轮先执行 unique *= available。之所以是乘法而不是重新计算连乘，是因为 $f(i) = f(i-1) \times (11 - i)$，递推关系让每轮只需一次乘法，避免了嵌套循环。

然后 total += unique。之所以在乘完之后再累加，是因为此刻的 unique 才是 $f(i)$，先加会把上一位数的结果重复计入。

最后 available--。之所以放在末尾，是因为它服务的是下一轮：这一轮用掉了一个数字位，下一轮的可选数量要减一。

循环结束返回 total。

以 n = 2 走一遍：n != 0，初值 total = 10、unique = 9、available = 9。进入循环 i = 2：unique = 9 * 9 = 81，含义是两位数中各位互异的有 81 个（首位 9 种、次位 9 种）；total = 10 + 81 = 91；available 降为 8。i = 3 时超过 n = 2，循环结束，返回 91。

人工核对：$[0, 100)$ 共 100 个数，各位重复的只有 11、22、33、44、55、66、77、88、99 这 9 个（一位数不可能重复），100 - 9 = 91，一致。

再以 n = 3 继续：接上一轮的 total = 91、unique = 81、available = 8。i = 3：unique = 81 * 8 = 648，即三位互异数有 648 个；total = 91 + 648 = 739；available 降为 7。返回 739。

最后检验 n = 0：直接命中特判返回 1，对应区间 $[0, 1)$ 中唯一的数 0，正确。

代码实现

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)$，凭据是循环只执行 n - 1 轮，每轮固定做一次乘法、一次加法和一次自减，且 n 不超过 8，实际是常数级别。

空间复杂度：$O(1)$，凭据是全程只维护 total、unique、available 三个整数变量，没有开数组也没有递归。

关键点总结

「统计满足某条件的数有多少个」优先考虑构造式计数而非枚举检验：直接数出能造出多少个合法对象，通常能把指数级的枚举降成线性甚至常数的公式。

「选过就不能再选」的约束对应排列数，逐位写出可选数量再连乘即可；如果顺序无关才用组合数，这一步判错会让答案差一个阶乘因子。

首位的特殊性（不能为 0）是数位类计数题的固定考点，必须把它从一般位中单独拆出来处理，否则会把前导零的情况重复计入。

连乘型公式应该写成递推迭代，用一个变量滚动保存上一项，避免每次从头重算导致的嵌套循环。

值域被题目上界（这里是 n <= 8）保护时可以放心用 int，但递推里保留「可选数量耗尽即停」的条件，能让代码在数学上自洽而不只是依赖数据保证。

面试视角：面试官会先看你能否把 $x < 10^n$ 翻译成「位数不超过 n」，再看你能否正确处理首位和 0。写完公式后常见追问是「如果要统计的是小于给定数 N 的互异数（1012 题）怎么办」，答案是改用数位 DP，按 N 的每一位逐位定界并用位掩码记录已用数字，能主动说出这个升级路径会明显加分。

易错点总结

n = 0 不特判：用例 n = 0，直接返回初值 total = 10，而正确答案是 1，因为区间 $[0, 1)$ 里只有 0。

total 初值写成 9：用例 n = 1，返回 9，漏掉了数字 0，正确答案是 10。

unique 初值写成 10：用例 n = 2，unique 变成 10 * 9 = 90，total = 10 + 90 = 100，把首位为 0 的两位数（如 01、02）也算了进去，正确答案是 91。

available 初值写成 10：用例 n = 2，unique = 9 * 10 = 90，次位可选数量没有扣除首位已用的那个，答案偏大。

循环从 i = 1 开始：用例 n = 1，会多执行一轮把 unique 变成 81 并加进 total，返回 91 而非 10。

先累加再相乘，把顺序写成 total += unique; unique *= available;：用例 n = 2，第一轮加的是 $f(1) = 9$ 而不是 $f(2) = 81$，返回 19 而非 91。

available-- 放在乘法之前：用例 n = 2，unique = 9 * 8 = 72，次位少算了一个可选数字，返回 82 而非 91。

用组合数 $C(10, k)$ 而不是排列数：用例 n = 2，$C(10,2) = 45$，忽略了数位的顺序性（12 和 21 是两个不同的数），答案严重偏小。

从 0 枚举到 $10^n - 1$ 逐个拆位判重：用例 n = 8，要检查 1 亿个数，每个还要做 8 次取模，在时限内跑不完。

用 Math.pow(10, n) 计算上界再做减法：用例 n = 8，浮点运算返回 1.0E8，转 int 时可能因精度问题得到 99999999，且这条路本身还要枚举，方向就错了。

认为答案需要对 $10^9+7$ 取模：用例 n = 8，答案 1808010 远小于 int 上界，取模不会改变结果但会让人误以为需要处理溢出，反而掩盖了「n 上界只有 8」这条关键约束。

相似题目

题目	难度	考察点
1012. 至少有 1 位重复的数字	困难	上界是任意整数 N 而非 $10^n$，必须用数位 DP 逐位定界后取补集
902. 最大为 N 的数字组合	困难	可用数字受限于给定集合且允许重复，考察定界下的分位计数
233. 数字 1 的个数	困难	统计的是数位出现次数而非数的个数，按位拆分做贡献法
46. 全排列	中等	同样的「选过不能再选」约束，但要真正构造出所有排列而非计数