剑指offer43:求1~n这n个整数中十进制表示中1出现的次数

66 阅读 0 评论 44 点赞

我是靠谱客的博主冷酷宝贝，最近开发中收集的这篇文章主要介绍剑指offer43:求1~n这n个整数中十进制表示中1出现的次数，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

转自：

https://www.cnblogs.com/wangkundentisy/p/8946858.html 和

https://blog.csdn.net/qq_22527013/article/details/90483820

如有侵权请联系删除

题意：

　　给定一个整数n，求1~n这n个整数中十进制表示中1出现的次数。

思路：

　　方法1：最直观的是，对于1~n中的每个整数，分别判断n中的1的个数，具体见《剑指offer》。这种方法的时间复杂度为O(N*logN)，当N比较大的时候，一般会超时。

　　方法2：这种类别的题目，如果直观求解不行的话，那么通常是进行找规律，转化成一个数学问题。这道题目在《编程之美》上有着比较详细的描述，下面就结合一个实例进行具体的分析：

在分析之前，首先需要知道一个规律：

从 1 至 10，在它们的个位数中，数字1出现了 1 次。
从 1 至 100，在它们的十位数中，数字1出现了 10 次。
从 1 至 1000，在它们的百位数中，数字1出现了 100 次。

依此类推，从 1 至 10i，在它们右数第二位中，数字1出现了10 ^ (i - 1)次。

对于 n = 2134,要找到从1 ~ 2134这2134个数字中所有1的个数。我们可以对2134进行逐位分析：

(1)在个位上，从1~2130，包含213个10，因此数字1出现了213次，剩下的数字2131、2132、2133、2134中个位数上只有2131包含树脂字1，剩下的都不包含。所以个位数上的数字1的总数为213 + 1 = 214。

(2)在十位上，从1 ~ 2100，包含了21个100，因此数字1出现了21 * 10 = 210次，剩下的数字从2101 ~ 2134，只有2110 ~ 2119这10个数字中十位的数字为1，所以十位上的数字1的总数为210 + 10 = 220。

(3)在百位上，从1 ~ 2000，包含了2个1000，因此数字1出现了2 * 100 = 200次，剩下的数字从2001 ~ 2134，只有2100 ~ 2134这35个数字中的百位的数字为1，所以百位数上数字1的总数为200 + 35= 235。

(4)在千位上，包含了0个10000，因此数字1出现了0 * 1000 = 0次，剩下的数字中只有1000 ~ 1999这1000个数字中的千位的数字为1，所以千位上的数字1的总数为1000。

因此从1 ~ 2134这n个数字中，数字出现的总的次数为 214 + 220 + 235 +1000 = 1669。

总结一下以上的步骤，可以得到这么一个规律：

对于数字n，计算它的第i(i从1开始，从右边开始计数)位数上包含的数字1的个数：

假设第i位上的数字为x的话，则

1.如果x > 1的话，则第i位数上包含的1的数目为：(高位数字 + 1）* 10 ^ (i-1) (其中高位数字是从i+1位一直到最高位数构成的数字)

2.如果x < 1的话，则第i位数上包含的1的数目为：(高位数字）* 10 ^ (i-1)

3.如果x == 1的话，则第i位数上包含1的数目为：(高位数字) * 10 ^ (i-1) +(低位数字+1) (其中低位数字时从第i - 1位数一直到第1位数构成的数字)

————————————————————————————————————————

如果还没懂的话，下面这段讲的更清楚（转自：https://blog.csdn.net/qq_22527013/article/details/90483820）：

对于一个形如xxxx的数，如要计算1出现在十位的数的个数，即xx1x的个数，分为三种情况

① xxab，a>1

a>1时，令a=1，则无论前面的两位xx取什么，都有相应的10个数可与之组合（如前面取23，后面可有10~19与其组合为2310~2319）

此时的数的取值为（xx+1）*10^(2-1) ——xx+1是因为，若xx为22，则可从0开始取值，一直到22，实际是23个取值；10^(2-1）是因为在十位上时，位置标志为2，然而与之相对应的只有10个数，需要2-1

② xxab，a=1

a=1时，a只有一种取值，即1，且受后面b的影响，与①的区别主要在于：当xx取到最高时（如2315时，23固定后，只能从10~15=6个数，而2325可从10~19=10个数），不再是10个数都是可取的，因此，分开计算

此时数的取值为(xx)*10^(2-1)+(b+1) ——前面xx其实是代表的xx-1+1，指的是从0开始取值，直到最高位-1（xx-1），当xx取最高位时，后面只能取10~1b——b+1个数

③ xxab，a=0

a=0时，xx0b，此时xx只能取到0~(xx-1)——共xx种取值，每种取值对应10^(2-1）个数

此时数的取值为（xx）*10^(2-1) ,当xx取最高位时，十位上无法出现1（因为超过了数本身）

【总结】

所以总的来说，对于从右到左数的第i位（位上数为x），出现1的次数为：

① x>1，(高位+1)*10^(i-1)

② x=1，(高位)*10^(i-1)+(低位+1)

③ x=0，(高位)*10^(i-1)
——————————————————————————————————

所以，代码如下：

int NumberOfDigitOne(int n) {
    if( n < 0)
        return 0;
    int i = 1;
    int high = n;
    int cnt = 0;
    while(high != 0)
    {
        high = n / pow(10 ,i);//high表示当前位的高位
        int temp = n / pow(10, i - 1);
        int cur = temp % 10;//cur表示第i位上的值，从1开始计算
        int low = n  - temp * pow(10, i - 1);//low表示当前位的低位
        if(cur < 1)
        {
            cnt += high * pow(10, i - 1);
        }
        else if(cur > 1)
        {
            cnt += (high + 1) * pow(10 ,i - 1);
 
        }
        else
        {
 
            cnt += high * pow(10, i - 1);
            cnt += (low + 1);
 
        }
        i++;
    }
    return cnt;
}

该算法的时间复杂度为O(logN)。

===================================================================================================================================
上述算法是计算数字1的个数，对于其他的数字k(1~9中的任意数字)，这个规律同样也是适用的，分析的过程也是一样的，只不过将上述的1改为k即可。下面代码是计算1 ~n中任意数字出现的次数：

int NumberOfDigitX(int n, int x) {
    if(x > 9 || x < 0 || n < 0)
        return 0;
    int i = 1;
    int high = n;
    int cnt = 0;
    while(high != 0)
    {
        high = n / pow(10 ,i);//high表示当前位的高位
        int temp = n / pow(10, i - 1);
        int cur = temp % 10;//cur表示第i位上的值，从1开始计算
        int low = n  - temp * pow(10, i - 1);//low表示当前位的低位
        if(cur < x)
        {
            cnt += high * pow(10, i - 1);
        }
        else if(cur > x)
        {
            cnt += (high + 1) * pow(10 ,i - 1);
 
        }
        else
        {
 
            cnt += high * pow(10, i - 1);
            cnt += (low + 1);
 
        }
        i++;
    }
    return cnt;
}

参考：http://www.cnblogs.com/cyjb/p/digitOccurrenceInRegion.html

附：求1~n中数字0的个数

int NumberOfDigitZero(int n) {
    if(n < 0)
        return 0;
    int i = 1;
    int high = n;
    int cnt = 0;
    while(high != 0)
    {
        high = n / pow(10 ,i);//high表示当前位的高位
        int temp = n / pow(10, i - 1);
        int cur = temp % 10;//cur表示第i位上的值，从1开始计算
        int low = n  - temp * pow(10, i - 1);//low表示当前位的低位
        if(cur < 0)//实际上这步不会执行
        {
            cnt += (high - 1) * pow(10, i - 1);
        }
        else if(cur > 0)
        {
            cnt += (high) * pow(10 ,i - 1);
 
        }
        else
        {
 
            cnt += (high - 1)* pow(10, i - 1);
            cnt += (low + 1);
 
        }
        i++;
    }
    return cnt;
}