试计算在区间 11 到 nn 的所有整数中，数字 xx（0\le x\le90≤x≤9）共出现了多少次？代码

算法1：暴力枚举

遍历区间 11 到 nn 的每个数，将每个数转换为字符串，判断字符串中是否包含数字 xx。

时间复杂度：O(nlogn)

算法2：数位分析

首先，我们需要知道在 0 到 n 中，数字 x 出现的次数。

对于一个数位为 d 的数字，如果最高位为 x，则它的最高位出现 x 的次数为：

1. 如果 x 不为 0，则最高位出现 x 的次数为 n / 10^{d} + 1。

2. 如果 x 为 0，则最高位出现 x 的次数为 n / 10^{d}。

如果最高位不为 x，则最高位出现 x 的次数为：

1. 如果 x 不为 0，则最高位出现 x 的次数为 (n / 10^{d} + 1) * 10^{d-1}。

2. 如果 x 为 0，则最高位出现 x 的次数为 (n / 10^{d}) * 10^{d-1}。

对于其他位数，如果当前位为 x，则：

1. 如果当前位为最高位，则出现次数为 n mod 10^{d-1} + 1。

2. 如果当前位不为最高位，则出现次数为 (n / 10^{d+1} + 1) * 10^{d}。

综上所述，我们可以从最高位开始，依次计算每一位上数字 x 出现的次数，然后相加得到总次数。

时间复杂度：O(logn)

C++ 代码：

相关问题

试计算在区间 11 到 nn 的所有整数中，数字 xx（0\le x\le90≤x≤9）共出现了多少次？

首先，我们可以计算出在 1 到 n 的所有整数中，数字 x 出现了多少次。具体的计算方法如下：

1. 对于个位数，假设 n 的个位数字为 k，则 1 到 n 中个位数字为 x 的数字个数为：

- 如果 x > k，则个位数字为 x 的数字有 (k / 10 + 1) * 10^(n-1) 个，其中 k / 10 表示小于 k 的十位数，+1 表示 k 自身，10^(n-1) 表示其他位可以任意取值；
- 如果 x = k，则个位数字为 x 的数字有 (k / 10) * 10^(n-1) + (n % 10) + 1 个，其中 k / 10 表示小于 k 的十位数，10^(n-1) 表示其他位可以任意取值，n % 10 表示剩余位数中可能出现的个数，+1 表示 k 自身；
- 如果 x < k，则个位数字为 x 的数字有 (k / 10) * 10^(n-1) 个，其中 k / 10 表示小于 k 的十位数，10^(n-1) 表示其他位可以任意取值。

2. 对于其他位数，假设 n 的第 i 位数字为 k，则 1 到 n 中第 i 位数字为 x 的数字个数为：

- 如果 x > k，则第 i 位数字为 x 的数字有 (k / 10^(i-1) + 1) * 10^(n-i) 个，其中 k / 10^(i-1) 表示小于 k 的前 i-1 位数字，+1 表示 k 自身，10^(n-i) 表示后面 n-i 位可以任意取值；
- 如果 x = k，则第 i 位数字为 x 的数字有 (k / 10^(i-1)) * 10^(n-i) + (n % 10^(i-1)) / 10^(i-1) * 10^(n-i-1) + 1 个，其中 k / 10^(i-1) 表示小于 k 的前 i-1 位数字，10^(n-i) 表示后面 n-i 位可以任意取值，(n % 10^(i-1)) / 10^(i-1) 表示剩余位数中可能出现的个数，/10^(i-1) 表示取第 i 位数字，*10^(n-i-1) 表示后面 n-i-1 位可以任意取值，+1 表示 k 自身；
- 如果 x < k，则第 i 位数字为 x 的数字有 (k / 10^(i-1)) * 10^(n-i) 个，其中 k / 10^(i-1) 表示小于 k 的前 i-1 位数字，10^(n-i) 表示后面 n-i 位可以任意取值。

最后，我们只需要将 0 到 9 的数字分别代入上述公式，计算出它们在 11 到 n 中出现的次数，相加即可得到答案。

试计算在区间 11 到 nn 的所有整数中，数字 xx（0\le x\le90≤x≤9）共出现了多少次？例如，在 11 到 1111 中，即在 1,2,3,4,5,6,7,8,9,10,111,2,3,4,5,6,7,8,9,10,11 中，数字 11 出现了 44 次。

我们可以分别计算数字 x 出现在个位、十位、百位……上的次数，再将它们相加即可。

对于个位上的情况，x 在个位上出现的次数为 $\lfloor \frac{n}{10}\rfloor$，即 n 中有多少个十位数。但是当 n 的个位数大于等于 x 时，x 也会出现在个位上，此时我们需要再加上 1。

对于十位、百位、千位等位置，我们可以使用类似的方法，只不过需要将 n 分解为相应的位数：十位上出现的次数为 $\lfloor \frac{n}{100}\rfloor$，百位上出现的次数为 $\lfloor \frac{n}{1000}\rfloor$，以此类推。

综上所述，数字 x 在区间 11 到 nn 的所有整数中出现的次数为：

$$\lfloor \frac{n}{10}\rfloor + (\text{n mod 10} \ge x) + 10\lfloor \frac{n}{100}\rfloor + 10(\text{n mod 100} \ge 10x) + 100\lfloor \frac{n}{1000}\rfloor + 100(\text{n mod 1000} \ge 100x) + \cdots$$

其中 mod 表示取模运算，$\lfloor \frac{n}{10}\rfloor$ 表示将 n 除以 10 取整。注意，当 n 小于 10 时，个位数不存在，此时只需要判断 n 是否等于 x 即可。

下面是 Python 代码实现：