题目概述
给定正整数 n,返回在 [1, n] 范围内具有 至少 1 位 重复数字的正整数的个数,其中$n \in [1,10^9]$
思路
题目要求计算至少1位重复数字的正整数的个数,如果直接穷举,$O(nlogn)$的复杂度会直接$TLE$,因此考虑采取容斥思想,计算没有重复数字的正整数的个数$res$,然后再用总数$n$减去$res$得到最后的答案。
求$res$可以考虑采取数位dp的思想,假设 $n$ 有 $sz$ 位,当前有 $cnt$ 个数还没使用且 $n$ 的第 $i$(从0开始计数) 位为 $nums[i]$ ,我们通过枚举在第 $i$ 位填 $[0,nums[i] - 1]$ ,对于剩下[i + 1,sz)的填数的方案数就等于$A_{cnt - 1}^{sz - i - 1}$。对于$nums[i]$,如果在之前出现了相同的数,就可以直接退出循环了(后面怎么填都已经有至少一个重复数字。否则,就假设第$i$位就是等于$nums[i]$然后继续枚举$i+1$位 。算完之后,再枚举一下长度为$[1,sz - 1]$的没有重复数字的正整数的个数(这个也是排列,只是要注意,第一位要是$[1,9]$ 。
需要注意的是,我们在枚举时,对于第$0$位我们填入的数应该为$[1,nums[i] - 1]$,因为我们是先求出长度为$sz$的没有重复数字的正整数的个数。
C++代码 $O(logn)$
class Solution {
public:
int numDupDigitsAtMostN(int n) {
int A[10][10] ;
for (int i = 0 ; i < 10 ; ++ i){
A[i][0] = 1;
for (int j = 1 ; j <= i ; ++ j)
A[i][j] = A[i][j - 1] * (i - j + 1) ;
}
int res = 0 ;
string nums ;
int t = n ;
while (t) nums += t % 10 + '0',t /= 10 ;
reverse(nums.begin(),nums.end()) ;
bool st[10] = {0} ;
int cnt = 10,sz = nums.size() ;
for (int i = 0 ; i < sz ; ++ i){
int num = nums[i] - '0' ;
for (int j = !i ; j < num ; ++ j){ // 枚举填数
if (st[j]) continue ;
res += A[cnt - 1][sz - i - 1] ;
}
if (st[num])
break ;
st[num] = 1;
--cnt ;
}
for (int i = 1 ; i < sz ; ++ i) // 枚举长度位[1,sz - 1]的无重复数
res += 9 * A[9][i - 1] ;
if (cnt + sz == 10) ++ res ; //如果n是无重复数,就将n计入
return n - res;
}
};