难度: Hard
给定正整数 n，返回在 [1, n] 范围内具有 至少 1 位 重复数字的正整数的个数。
示例 1：
输入：n = 20 输出：1 解释：具有至少 1 位重复数字的正数（<= 20）只有 11 。
示例 2：
输入：n = 100 输出：10 解释：具有至少 1 位重复数字的正数（<= 100）有 11，22，33，44，55，66，77，88，99 和 100 。
示例 3：
输入：n = 1000 输出：262
提示：
1 <= n <= 109
Submission
运行时间: 32 ms
内存: 0.0 MB
class Solution:
def numDupDigitsAtMostN(self, N: int) -> int:
res = 0
M = [int(i) for i in str(N + 1)]
length = len(M)
def fac(m, n):
result = 1
for _ in range(n):
result *= m
m -= 1
return result
for i in range(1, length):
res += 9 * fac(9, i - 1)
seen = set()
for i in range(len(M)):
for j in range(0 if i else 1, M[i]):
if j not in seen:
res += fac(9 - i, length - i - 1)
if M[i] in seen:
break
seen.add(M[i])
return N - res
Explain
这个解法使用的是组合数学中的排列组合原理来解决问题。首先，算法试图计算从1到N所有不包含重复数字的数的数量，然后从总数N中减去这个值来得到至少包含一个重复数字的数的数量。算法首先计算较短的长度（如1位数，2位数等）的所有可能的不重复数字的组合。对于每一个长度，我们首先选择第一位数字（不能为0除了长度为1的情况），然后选择剩余位置的数字（可以从剩余的9个数字中选择）。然后，算法检查N自身的每一位，确保之前的数字没有重复，并计算剩余位的可能性。如果在任何点发现重复，循环将停止。
时间复杂度: O(L^2) 其中 L 是 N 的位数长度，这可以近似为 O((log N)^2)
空间复杂度: O(L) 其中 L 是 N 的位数长度
class Solution:
def numDupDigitsAtMostN(self, N: int) -> int:
res = 0 # 初始化结果变量
M = [int(i) for i in str(N + 1)] # 将数字N+1的每一位转化为数组
length = len(M) # 数字的长度
def fac(m, n): # 定义阶乘函数，用于计算排列数
result = 1
for _ in range(n): # 计算m*(m-1)*...*(m-n+1)
result *= m
m -= 1
return result
for i in range(1, length): # 计算所有位数少于N的不包含重复数字的数
res += 9 * fac(9, i - 1)
seen = set() # 存储已见的数字，用于检测重复
for i in range(len(M)): # 检查N自身
for j in range(0 if i else 1, M[i]): # 避免首位为0
if j not in seen:
res += fac(9 - i, length - i - 1) # 如果未见过，计算剩余位的组合
if M[i] in seen:
break # 如果见过，则中断
seen.add(M[i]) # 添加当前数字到已见集
return N - res # 计算包含至少一个重复数字的数的数量
Explore
算法通过计算数字N+1的长度来确定所有小于N的位数。例如，如果N是999，那么N+1就是1000，长度为4。因此，算法会计算1位数、2位数、3位数的所有可能组合，这些都是小于N的位数。对于每个位数，算法计算可能的不重复数字的组合数量。
在多位数中，如果第一位数字为0，则这个数字实际上会变成一个更短的数字（例如，'0123'实际上是'123'）。这会使数字的位数减少，导致其不符合原始位数的定义。因此，第一位数字不能为0以确保数字的位数正确，而唯一的例外是单一位数，因为0本身就是一个有效的单一位数。
在fac函数中使用循环而不是递归是为了提高性能和避免深度递归可能导致的栈溢出问题。循环通常比递归更为高效，因为递归需要多次调用函数自身，这增加了调用开销和内存使用。此外，循环易于理解和维护。虽然Python提供了内置的阶乘函数，但在这种情况下定义一个自定义的阶乘函数可以更清楚地控制函数的行为，特别是在不需要计算完整阶乘而只需要计算部分乘积的情况下。
在检查N自身的每一位数字时，算法使用了一个集合来跟踪已经看到的数字，这样可以快速检查和插入操作，每个操作的平均时间复杂度为O(1)。此外，通过逐位检查并在发现重复时立即停止进一步的检查，算法尽早终止无用的计算，从而提高效率。这种方法特别适用于大数字，因为它避免了不必要的全部迭代，尤其是在一旦发现重复数字后，剩余的位数不再需要进一步计算。