题目描述

给定正整数 N，返回小于等于 N 且具有至少 1 位重复数字的正整数。

样例

示例 1：

输入：20
输出：1
解释：具有至少 1 位重复数字的正数（<= 20）只有 11 。
示例 2：

输入：100
输出：10
解释：具有至少 1 位重复数字的正数（<= 100）有 11，22，33，44，55，66，77，88，99 和 100 。
示例 3：

输入：1000
输出：262


提示：

1 <= N <= 10^9

算法1

(数位DP) $O(2048logn)$

具体见代码注释

时间复杂度分析：$O(2048logn)$

Python3 代码

class Solution:
    def numDupDigitsAtMostN(self, N: int) -> int:
        # self.length表示正整数N一共有多少位
        self.length = 0
        self.nums = []
        while N:
            self.length += 1
            self.nums.append(N % 10)
            N //= 10
        self.dp = [[[-1 for _ in range(2)] for _ in range(1024)] for _ in range(self.length)]

        # flag表示当前搜索结果中整数的位数是否和N一样
        # lead表示当前搜索整数是否有前导0
        # succ表示枚举这一位以前有没有重复
        # state换算成二进制有10位，分别表示枚举到这一位之前0~9有没有被使用
        # pos表示当前枚举位置
        def dfs(pos, state, succ, lead, flag):
            # 完成枚举最后一位，返回succ，succ=1表示有重复的数字，succ=0表示没有重复的数字
            if pos == -1:
                return succ
            # 记忆化，如果位数小于N，没有前导0，而且结果已经被求出来，则直接返回
            if not flag and not lead and self.dp[pos][state][succ] != -1:
                return self.dp[pos][state][succ]
            # limit表示枚举上限
            limit = self.nums[pos] if flag else 9
            # start表示枚举下限
            start = 1 if lead else 0
            # 返回结果清零
            res = 0
            for i in range(start, limit + 1):
                res += dfs(pos - 1, state|(1<<i), succ|((state>>i)&1), False, (flag and i==limit))
            # 对应前面记忆化
            if not flag and not lead:
                self.dp[pos][state][succ] = res
            return res

        ans = 0
        for i in range(self.length - 1, -1, -1):
            ans += dfs(i, 0, 0, True, i==self.length - 1);
        return ans

算法2

(搜索算法) $O(logn)$

先计算位数小于N并且所有位都不重复的数字个数，再用搜索算法搜索小于N且位数等于N且所有位都不重复的数字个数，最后返回N减去这些所有位都不重复的数字个数即为答案。

时间复杂度分析：$O(logn)$

Python3 代码

class Solution:
    def numDupDigitsAtMostN(self, N: int) -> int:
        if N < 10:
            return 0
        bit_count = 0
        t = N
        bits = [0] * 10
        no_dup = 0
        while t > 0:
            bits[bit_count] = t % 10
            bit_count += 1
            t //= 10
        bit_count = min(bit_count, 10)

        for i in range(bit_count - 1):
            temp = 9
            cur = 9
            for j in range(i):
                temp *= (9-j)
            no_dup += temp

        def helper(remain, mx, used, is_first, need_mx):
            nonlocal no_dup, bits
            if remain == 0:
                no_dup += 1
                return
            candidates = set(range(mx + 1)) - used
            if is_first:
                candidates -= {0}
            remain -= 1
            for candidate in candidates:
                if need_mx and candidate == mx:
                    helper(remain, bits[remain-1], used | {candidate}, False, True)
                else:
                    p = 9 - len(used)
                    temp = 1
                    for i in range(remain):
                        temp *= p
                        p -= 1
                    no_dup += temp
        helper(bit_count, bits[bit_count-1], set(), True, True)

        return N - no_dup

算法3

(排列组合数计算) $O(logn)$

与算法2思路相同，只不过在计算小于N且位数等于N且所有位都不重复的数字个数时候，从高位向低位枚举，用一个集合s来记录前面已经用过的数字，枚举第i位时，第i位往后的数字选择只有9-i种了，取其中n-i-1个进行全排列，将排列个数加在统计结果中，最后将这一位上的数字也加进集合s。最后用N减去统计结果即为答案。

时间复杂度分析：$O(logn)$

Python3 代码

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

        def A(n, m):
            return math.factorial(n) // math.factorial(n - m)

        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