本文共 1818 字，大约阅读时间需要 6 分钟。

计算从1到n中数字“1”出现次数的高效方法

问题描述

给定一个整数n，要求计算从1到n中所有整数的十进制表示中数字“1”出现的总次数。

解决思路

为了高效解决这个问题，我们需要采取一种数学上的分解与分析方法，而不是简单地逐一枚举和计算（这种方法在n较大的情况下会导致时间复杂度过高）。以下是详细的分析方法：

数字的结构分解

当我们将一个数用十进制表示时，可以将其视为一个多位数的结构。例如，数123可以表示为百位、十位、个位的三个部分：1,2,3。

我们可以从右到左逐步分析每一位数字的贡献。这个方法的核心是从低位到高位逐步计算每一位数字“1”出现的次数，并结合其所在的位权来计算总贡献。

每一位的贡献分析

假设我们分析的是当前数的第i位（从右往左数，第一位是个位，第二位是十位，依此类推）。我们需要计算以下三种情况：

然后，我们结合当前位的位权来计算总贡献。

位权计算方法

对于第i位，位权是10的(i-1)次方。例如，个位的位置是1（10^0），十位的位置是10（10^1），依此类推。

具体计算步骤

假设我们有一个数n，十进制表示为d_k d_{k-1} ... d_1，其中d_k是最高位，d_1是个位。

我们需要对每一位d_i进行分析：

代码实现示例

以下是一个实现了上述逻辑的C++代码：

int numberOf1Between1AndN(int n) {    if (n == 0) return 0;    vector
   
     digits;    while (n) {        digits.push_back(n % 10);        n /= 10;    }    int ans = 0;    for (int i = digits.size() - 1; i >= 0; --i) {        int left = 0;        int right = 0;        int power = 1;        for (int j = digits.size() - 1; j > i; --j) {            left = left * 10 + digits[j];        }        for (int j = i - 1; j >= 0; --j) {            right = right * 10 + digits[j];            power *= 10;        }        ans += left * power;        if (digits[i] == 1) {            ans += right + 1;        } else if (digits[i] > 1) {            ans += power;        }    }    return ans;}
   

代码解释

这种方法的时间复杂度与数字的位数有关，而不是与n的大小有关，因此它是高效的。