整数中1出现的次数(从1到n整数中1出现的次数)

整数中1出现的次数(从1到n整数中1出现的次数)

题目描述

求出1 ~ 13的整数中1出现的次数,并算出100 ~ 1300的整数中1出现的次数？为此他特别数了一下1 ~ 13中包含1的数字有1、10、11、12、13因此共出现6次,但是对于后面问题他就没辙了。ACMer希望你们帮帮他,并把问题更加普遍化,可以很快的求出任意非负整数区间中1出现的次数。

规律( 1 的数目)

如果第 i 位(自右向左，从1开始标号)上的数字是0，则第 i 位可能出现 1 的次数由更高位决定(若没有高位，则视高位为0)，等于更高位数乘以当前位数的权重(10^i-1)

如果第 i 位上的数字为 1，则第 i 位上出现 1 的次数不仅受更高位影响，还受低位影响(若没有低位，视低位为0)，等于更高位数乘以当前位数的权重 (10^i-1) + (低位数 + 1)

如果第 i 位上的数字大于 1，则第 i 位上可能出现 1 的次数仅由更高位决定(若没有高位，视高位为0)，等于(更高位数 + 1)乘以当前位数的权重 (10^i-1)

规律(x 的数目)

这里的 x 属于[1, 9]， 因为 x = 0 不符合下列规律，需要单独计算

首先要知道以下规律

• 从 1 至 10，在它们的个位数中，任意的 x 都出现了 1 次
• 从 1 至 100，在它们的十位数中，任意的 x 都出现了 10 次
• 从1至1000，在它们的百位数中，任意的x都出现了100次
• 依次类推，从 1 至 10ⁱ，在它们的左数第二位(右数第 i 位)，任意的 x 都出现了 (10^i-1)次。这个规律很容易验证，这里不再多做说明

接下以 n = 2593, x = 5 为例来解释如何得到数学公式。从 1 至 2593中，数字 5 总计出现了 813 次，其中有 259次出现在个位，260次出现在十位，294次出现在百位，0次出现在千位

• 现在依次分析这些数据，首先是个位。从 1 至 2590 中，包含了 259 个 10，因此任意的 x 都出现了 259 次。最后剩余的三个数 2531,2592,2593，因为它们最大的个位数字 3 < x。因此不会包含任何 5. (也可以这么看， 3 < x， 则个位上可能出现的 x 的位数由更高位决定，等于更高位数字 (259) * 10^1-1 = 259)。

• 然后是十位。从 1 至 2500中，包含了25个100，因此任意的 x 都出现了 25 * 10 = 250 次。剩下的数字从 2501 至 2593，它们最大的十位数是 9 > x，因此会包含全部 10 个 5。最后总计 250 + 10 = 260。(也可以这么看，9 > x，则十位上可能出现的 x 的位数由更高位决定，等于更高位数字(25 + 1) * 10^2-1 = 260)

• 接下来是百位。从1至2000中，包含了2个1000，因此任意x都出现了2 * 100 = 200次。剩下的数字从2001至2593，它们最大的百位数字5 == x，这时候情况就略微复杂，它们的百位肯定是包含5的，但是不会包含全部100个。如果把百位是5的列出来，是从2500至2593，数字的个数与十位和个位数字有关，是93 + 1 = 94。最后总计 200 + 94 = 294。(也可以这么看， 5 == x，则百位上可能出现的x次数不仅受跟高位影响，还受低位影响，等于更高位数字 2 * 10^3-1 + (93 + 1))

• 最后是千位，现在已经没有更高位，因此直接看最大的千位数字 2 < x，因此不会包含任何 5 。(也可以这么看，2 < x，则千位上可能出现的x的次数仅由更高位决定，等于更高位数字 0 * 10^4-1 = 0)

到此为止，已经计算出全部数字 5 的出现次数。

总结

总结一下以上的算法，可以看到，当计算右数第 i 位包含的 x 的个数时：

• 取第 i位左边(高位)的数字，乘以 10^i-1，得到基础值 a

• 取第 i 位数字，计算修正值

• 如果大于 x , 则结果为 a + 10^i-1

• 如果小于 x，则结果为 a

• 如果等于 x，则取第 i 位右边(低位)数字，设为 b，最后结果为 a + b + 1

代码

class Solution {
public:
    int NumberOf1Between1AndN_Solution(int n)
    {
    	if(n < 1) return 0;
        if(n < 9) return 1;

        int high = 0;
        int k = 0;
        int cur = 0;
        int count = 0;

        for(int i = 1; k = n / i; i *= 10){
            high = k / 10;

            count += high * i;

            cur = k % 10;
            if(cur > 1)
                count += i;
            else if(cur == 1)
                count += n - k * i + 1;
        }

        return count;
    }
};