题目描述

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

样例

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

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

输入：1000
输出：262

注意

• 1 <= N <= 10^9

算法

(数位统计) $O((\log n)^2)$

1. 题目要求的是至少 1 位重复正整数的个数，难以统计，不妨统计所有数位都不重复的正整数的个数。
2. 首先统计数位个数少于 N 的数字个数，运用排列计数规则很容易计算出来。假设数位为 1 位，则个数为 9 个；假设数位为 L (> 1) 位，则个数为 $9 * 9 * 8 * 7 * \cdots * (9 - L + 2)$。
3. 然后考虑数位个数等于 N 的数字个数，这里我们从高位到低位统计。假定当前位填不超过 N 当前位的数字，然后同样运用以上规则，统计个数；然后再将这一位固定为 N 当前位的数字，继续向低位统计。统计过程中，如果出现了重复用的数字，即 N 本身就有重复数字，则直接返回 N - ans 即可。最后，返回 N - ans - 1 这里减的 1 就是 N 本身。
4. 以数字 34 为例，首先统计出数位为 1 位的个数，显然为 9 个。然后尝试最高位填 1 和 2，填好之后，第二位都有 9 种填法，故这样有 18 种。然后固定最高位为 3，填下一位。下一位可以填 0, 1, 2，共有 3 种，所以答案为 34 - 9 - 18 - 3 - 1 = 3。

时间复杂度

• 需要两层循环遍历数字 N 的数位，故时间复杂度为 $O((\log n)^2)$，可以通过一些优化使时间复杂度达到 $O(\log n)$。

空间复杂度

• 仅需要 $O(\log n)$ 的空间将数字 N 的各个数位取出。

C++ 代码

class Solution {
public:
    int numDupDigitsAtMostN(int N) {
        string n(to_string(N));
        reverse(n.begin(), n.end());
        int ans = 0;
        for (int len = 1; len <= n.length() - 1; len++) {
            int tmp = 9;
            for (int j = 9, k = len - 1; k >= 1; k--, j--)
                tmp *= j;
            ans += tmp;
        }

        vector<bool> used(10, false);

        for (int i = n.length() - 1; i >= 0; i--) {
            int tmp = 0;
            for (int j = 0; j < n[i] - '0'; j++)
                if (!used[j])
                    tmp++;
            if (i == n.length() - 1)
                tmp--;

            if (tmp > 0) {
                for (int j = 10 - (n.length() - i), k = i - 1; k >= 0; k--, j--)
                    tmp *= j;
                ans += tmp;
            }
            if (used[n[i] - '0'])
                return N - ans;
            used[n[i] - '0'] = true;
        }
        return N - ans - 1;
    }
};