题目描述

给定一个非负整数 $n$，请统计共有多少个数 $x$，它的每位数字互不相同，且满足 $0 \le x \lt n$

样例

输入：2
输出：91 
解释：答案是0到99之间的所有数，除去11，22，33，44，55
      66，77，88，99，共91个数。

算法

(乘法原理) $O(1)$

首先总共有0-9十个不同的数字，所以我们只需要考虑 $n \le 10$ 的情况。

然后我们从最高位开始计数，为了方便，我们先不考虑 $x = 0$ 的情况：

1. 最高位不能选0，只有9种选法；
2. 次高位不能和最高位相同，但可以选0，有9种选法；
3. 下一位不能和前两位相同，有8种选法；
4. 以此类推，枚举 $n$ 位；

最后根据乘法原理，把每一位的选法数量相乘就是总方案数。
最后不要忘记加上 $x=0$ 的情况，让答案加1。

时间复杂度分析：我们最多考虑10位数字，最多只有一重循环，循环10次。所以时间复杂度是 $O(1)$。

C++ 代码

class Solution {
public:
    int countNumbersWithUniqueDigits(int n) {
        if (!n) return 1;
        n = min(n, 10);
        vector<int> f(n);
        f[0] = 9;
        for (int i = 1; i < n; i ++ ) f[i] = f[i - 1] * (10 - i);
        int res = 0;
        for (int i = 0; i < n; i ++ ) res += f[i];
        return res + 1;
    }
};