GESP二级 NOIP201301 计数问题 - 统计数字出现次数的算法详解

GESP二级 NOIP201301 计数问题 - 统计数字出现次数的算法详解

问题描述: 试计算在区间 1 到 n 的所有整数中，数字 x(0≤x≤9)共出现了多少次？例如，在 1 到 11 中，即在 1,2,3,4,5,6,7,8,9,10,11 中，数字 1 出现了 4 次。

输入描述: 2 个整数 n, x，之间用一个空格隔开。

输出描述: 1 个整数，表示 x 出现的次数。

用例输入 1: 11 1 用例输出 1: 4

用例输入 2: 2 1 用例输出 2: 1

提示: 对于 100%的数据，1≤n≤1,000,000,0≤x≤9。

解题思路: 我们可以将数字 x 出现的次数分为两部分来计算：

1. 在每个数字位上出现的次数: 我们可以将每个数字位上的数字分为三种情况：

   • 当前位上的数字小于 x，那么当前位上数字 x 出现的次数为：更高位的数字 * 当前位数。
   • 当前位上的数字等于 x，那么当前位上数字 x 出现的次数为：更高位的数字 * 当前位数 + 低位数字 + 1。
   • 当前位上的数字大于 x，那么当前位上数字 x 出现的次数为：(更高位的数字 + 1) * 当前位数。

2. 最高位上出现的次数: 最高位上的数字 x 出现的次数为：(更高位的数字 + 1) * 当前位数。

算法步骤:

1. 将整数 n 转换为字符串，计算字符串的长度 len。
2. 初始化结果 res 为 0。
3. 从高位到低位遍历字符串的每个字符：
   • 将当前字符转换为数字 cur。
   • 将字符串的前缀转换为数字 prefix，后缀转换为数字 suffix。
   • 如果 cur < x，则 res += prefix * pow(10, len-1)。
   • 如果 cur == x，则 res += prefix * pow(10, len-1) + suffix + 1。
   • 如果 cur > x，则 res += (prefix + 1) * pow(10, len-1)。
   • 如果 cur == x，更新 suffix = suffix * 10 + cur。
   • 更新 len -= 1。
4. 返回结果 res。

算法复杂度: 时间复杂度：O(logn)。其中 n 是输入的整数。 空间复杂度：O(1)。