0357. 统计各位数字都不同的数字个数【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 排列组合

1. 📝 题目描述

• leetcode

给你一个整数 n，统计并返回各位数字都不同的数字 x 的个数，其中 0 <= x < 10^n。

---

示例 1：

输入：n = 2
输出：91
解释：答案应为除去 11、22、33、44、55、66、77、88、99 外，在 0 ≤ x < 100 范围内的所有数字。

示例 2：

输入：n = 0
输出：1

---

提示：

• 0 <= n <= 8

2. 🎯 s.1 - 排列组合

c

int countNumbersWithUniqueDigits(int n) {
    if (n == 0) return 1;
    int res = 10, product = 9;
    for (int i = 2; i <= n && i <= 10; i++) {
        product *= (10 - i + 1);
        res += product;
    }
    return res;
}

js

/**
 * @param {number} n
 * @return {number}
 */
var countNumbersWithUniqueDigits = function (n) {
  if (n === 0) return 1
  let res = 10,
    product = 9
  for (let i = 2; i <= n && i <= 10; i++) {
    product *= 10 - i + 1
    res += product
  }
  return res
}

py

class Solution:
    def countNumbersWithUniqueDigits(self, n: int) -> int:
        if n == 0:
            return 1
        res, product = 10, 9
        for i in range(2, min(n, 10) + 1):
            product *= (10 - i + 1)
            res += product
        return res

• 时间复杂度：$O(n)$
• 空间复杂度：$O(1)$

算法思路：

• $i$ 位数且各位不同的个数 = $9\times 9\times 8\times \cdots \times (10-i+1)$
• 累加 1 位到 $n$ 位的结果，加上 $n=0$ 的情况