1012._Numbers_With_1_Repeated_Digit.md

# 1012. Numbers With 1 Repeated Digit

**<font color=red>难度: Hard</font>**

## 刷题内容

> 原题连接

* https://leetcode.com/problems/numbers-with-1-repeated-digit/

> 内容描述

```
Given a positive integer N, return the number of positive integers less than or equal to N that have at least 1 repeated digit.

 

Example 1:

Input: 20
Output: 1
Explanation: The only positive number (<= 20) with at least 1 repeated digit is 11.
Example 2:

Input: 100
Output: 10
Explanation: The positive numbers (<= 100) with atleast 1 repeated digit are 11, 22, 33, 44, 55, 66, 77, 88, 99, and 100.
Example 3:

Input: 1000
Output: 262
 

Note:

1 <= N <= 10^9
```

## 解题方案

> 思路 1
******- 时间复杂度: O(lgN)******- 空间复杂度: O(lgN)******


算有重复的，我们可以先算出没有重复的，然后返回`(总数-没有重复)`即可

比赛中我想到了可以这样做，但是实现的时候TLE了，赛后看了[[Java/Python] Count the Number Without Repeated Digit](https://leetcode.com/problems/numbers-with-1-repeated-digit/discuss/256725/JavaPython-Count-the-Number-Without-Repeated-Digit)

那么没有重复怎么算呢？

对于一个N位digit的数字，小于等于它的没有重复的有以下两种：
1. digit数小于N的，对于这部分，直接算即可
2. digit数小于N的，对于这部分，我们必须要让构造出的数字小于等于N


```python
class Solution:
    def numDupDigitsAtMostN(self, N):
        L = list(map(int, str(N + 1)))
        res, n = 0, len(L)

        def A(m, n):
            return 1 if n == 0 else A(m, n - 1) * (m - n + 1)

        for i in range(1, n): 
            res += 9 * A(9, i - 1)
        s = set()
        for i, x in enumerate(L):
            for y in range(0 if i else 1, x):
                if y not in s:
                    res += A(9 - i, n - i - 1)
            if x in s: 
                break
            s.add(x)
        return N - res
```

For anyone who doesn't understand the function `def A()`, you can see the iterative version of it below.
```python
        def A(m, n):
            res = 1
            for i in range(n):
                res *= m
                m -= 1
            return res
```
It means the `permutation` of `m * (m-1) * ... * (m-(n-1))`.

And for why use `9*A(9,i-1)` instead of `A(9,i)`, that's because there should be no leading `0`, but the following digit can be `0`.


***将函数A重命名为permu***

```python
class Solution:
    def numDupDigitsAtMostN(self, N):
        L = list(map(int, str(N + 1)))
        res, n = 0, len(L)

        def permu(m, n):
            res = 1
            for i in range(n):
                res *= m
                m -= 1
            return res

        for i in range(1, n): 
            res += 9 * permu(9, i - 1)
            
        s = set()
        for i, x in enumerate(L):
            for y in range(0 if i else 1, x):
                if y not in s:
                    res += permu(9 - i, n - i - 1)
            if x in s: 
                break
            s.add(x)
        return N - res
```