countDigitOne.md

1 ~ n 整数中 1 出现的次数

题目:输入一个整数 n ，求 1 ~ n 这 n 个整数的十进制表示中 1 出现的次数。

例如，输入 12，1 ~ 12 这些整数中包含 1 的数字有 1、10、11 和 12，1 一共出现了 5 次。

示例 1：

// 输入：n = 12
// 输出：5

示例 2：

// 输入：n = 13
// 输出：6

限制：

• 1 <= n < 2 ^ 31

思路分析

本题难度很大，需要从题意中找出数学规律。根据题意，我们可以理解为，求 1 ~ n 的个位、十位、百位 ... 的 1 出现的次数相加，即为 1 出现的总次数。

设数字 n 是一个 x 位数，记数字 n 的第 i 位数位 n_i,则数字 n 可以表示为 n_xn_x-1...n₂n₁。

• 将 n_i 称为当前位，记为 cur。
• 将 n_i-1n_i-2...n₂n₁ 称为低位，记为 low。
• 将 n_xn_x-1...n_i+2n_i+1 称为高位,记为 high。
• 将 10ⁱ 称为位因子，记为 digit。

然后，我们计算某位中 1 出现的次数的计算方法如下:

根据当前位 cur 的值的不同，我们可以分成三种情况:

1. 当 cur = 0 时: 此时 1 的出现次数只由高位来决定(因为低位一定全是 0)，计算公式为:high * digit。

如下图所示，以 n = 2304 为例，求 digit = 10 （即十位）的 1 出现次数。

2. 当 cur = 1 时: 此时 1 的出现次数由高位与低位来决定，计算公式为:high * digit + low + 1(加 1 就是包含当前位)

如下图所示，以 n = 2314 为例，求 digit = 10 （即十位）的 1 出现次数。

3. 当 cur = 2 时: 此时 1 的出现次数由高位来决定，计算公式为:(high + 1) * digit(之所以要加 1 再乘以 10，就是包含当前位出现 1 的次数)。

如下图所示，以 n = 2324 为例，求 digit = 10 （即十位）的 1 出现次数。

根据前面的三点分析，我们从而可以推导出递推公式，当然再推导出公式之前，我们应该先初始化high,cur,low,digit的初始值，如下所示:

high = Math.floor(n / 10);
cur = n % 10;
low = 0;
digit = 1;

因此，从个位到最高位的推导公式即为:

//当最高位或者当前位为0的时候，则代表已经越过了最高位
while (high !== 0 || cur !== 0) {
  low += cur * digit; //下一轮的低位应该是当前位与位因子的乘积
  cur = high % 10; //下一轮的当前位应该是最高位与位因子的求余
  high = Math.floor(high / 10); //下一轮的最高位应该除以位因子
  digit = digit * 10; //每一轮的位因子也是10的倍数
}

根据以上的三种情况的分析和推导公式，我们就可以得到本题的解法:

/**
 * @param {number} n
 * @return {number}
 */
var countDigitOne = function (n) {
  //初始化
  let low = 0, //最低位
    d = 1, //位因子
    high = Math.floor(n / 10), //最高位
    cur = n % 10; //当前位
  //结果值
  let res = 0;
  while (high !== 0 || cur !== 0) {
    if (cur === 0) {
      //当前位是0的时候,计算公式为最高位与位因子的乘积
      res += high * d;
    } else if (cur === 1) {
      //当前位是1的时候，计算公式为最高位与位因子加上最低位加上当前位之和
      res += high * d + low + 1;
    } else {
      //当前位是2 ~ 9的时候，计算公式为最高位与位因子的乘积和当前位与位因子的乘积之和
      res += (high + 1) * d;
    }
    low += cur * d; //计算最低位
    cur = high % 10; //计算当前位
    high = Math.floor(high / 10); //计算最高位
    d *= 10; //计算位因子
  }
  //返回结果
  return res;
};

• 时间复杂度 O(log ⁿ) ： 循环内的计算操作使用 O(1) 时间；循环次数为数字 n 的位数，即 log₁₀ⁿ，因此循环使用 O(logⁿ)时间。
• 空间复杂度 O(1)： 几个变量使用常数大小的额外空间。

更多解法见精选答案。