0357-统计各位数字都不同的数字个数

Raphael Liu Lv10

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

示例 1:

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

示例 2:

**输入:** n = 0
**输出:** 1

提示:

  • 0 <= n <= 8

方法一:排列组合

思路

首先考虑两种边界情况:

  • 当 $n = 0$ 时,$0 \le x \lt 1$,$x$ 只有 $1$ 种选择,即 $0$。

  • 当 $n = 1$ 时,$0 \le x \lt 10$,$x$ 有 $10$ 种选择,即 $0 \sim 9$。

当 $n = 2$ 时,$0 \le x \lt 100$,$x$ 的选择可以由两部分构成:只有一位数的 $x$ 和有两位数的 $x$。只有一位数的 $x$ 可以由上述的边界情况计算。有两位数的 $x$ 可以由组合数学进行计算:第一位的选择有 $9$ 种,即 $1 \sim 9$,第二位的选择也有 $9$ 种,即 $0 \sim 9$ 中除去第一位的选择。

更一般地,含有 $d$ ($2 \le d \le 10$)位数的各位数字都不同的数字 $x$ 的个数可以由公式 $9 \times A_9^{d-1 计算。再加上含有小于 $d$ 位数的各位数字都不同的数字 $x$ 的个数,即可得到答案。

代码

[sol1-Python3]
1
2
3
4
5
6
7
8
9
10
11
class Solution:
def countNumbersWithUniqueDigits(self, n: int) -> int:
if n == 0:
return 1
if n == 1:
return 10
res, cur = 10, 9
for i in range(n - 1):
cur *= 9 - i
res += cur
return res
[sol1-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
int countNumbersWithUniqueDigits(int n) {
if (n == 0) {
return 1;
}
if (n == 1) {
return 10;
}
int ans = 10, cur = 9;
for (int i = 0; i < n - 1; ++i) {
cur *= 9 - i;
ans += cur;
}
return ans;
}
};
[sol1-Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public int countNumbersWithUniqueDigits(int n) {
if (n == 0) {
return 1;
}
if (n == 1) {
return 10;
}
int res = 10, cur = 9;
for (int i = 0; i < n - 1; i++) {
cur *= 9 - i;
res += cur;
}
return res;
}
}
[sol1-C#]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class Solution {
public int CountNumbersWithUniqueDigits(int n) {
if (n == 0) {
return 1;
}
if (n == 1) {
return 10;
}
int res = 10, cur = 9;
for (int i = 0; i < n - 1; i++) {
cur *= 9 - i;
res += cur;
}
return res;
}
}
[sol1-Golang]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
func countNumbersWithUniqueDigits(n int) int {
if n == 0 {
return 1
}
if n == 1 {
return 10
}
ans, cur := 10, 9
for i := 0; i < n-1; i++ {
cur *= 9 - i
ans += cur
}
return ans
}
[sol1-C]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
int countNumbersWithUniqueDigits(int n) {
if (n == 0) {
return 1;
}
if (n == 1) {
return 10;
}
int ans = 10, cur = 9;
for (int i = 0; i < n - 1; ++i) {
cur *= 9 - i;
ans += cur;
}
return ans;
}
[sol1-JavaScript]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
var countNumbersWithUniqueDigits = function(n) {
if (n === 0) {
return 1;
}
if (n === 1) {
return 10;
}
let res = 10, cur = 9;
for (let i = 0; i < n - 1; i++) {
cur *= 9 - i;
res += cur;
}
return res;
};

复杂度分析

  • 时间复杂度:$O(n)$。仅使用一个循环。

  • 空间复杂度:$O(1)$。仅使用常数空间。

 Comments
On this page
0357-统计各位数字都不同的数字个数