[算法系列之三十二]1的数目

骑猪看日落 2023-06-25 03:08 36阅读 0赞

**题目**

> Given an integer n, count the total number of digit 1 appearing in all non-negative integers less than or equal to n.
> 
> For example:  
> Given n = 13,  
> Return 6, because digit 1 occurred in the following numbers: 1, 10, 11, 12, 13.

**思路一**

这个问题看上去并不是一个困难的问题，因为不需要太多的思考，我想大家都能找到一个最简单的方法来计算f（N），那就是从1开始遍历到N，将其中每一个数中含有“1”的个数加起来，自然就得到了从1到N所有“1”的个数的和。

这个方法很简单，只要学过一点编程知识的人都能想到，实现也很简单，容易理解。但是这个算法的致命问题是效率，它的时间复杂度是O（N）×计算一个整数数字里面“1”的个数的复杂度 = O（N \* log2 N）。如果给定的N比较大，则需要很长的运算时间才能得到计算结果。比如在笔者的机器上，如果给定N=100 000 000，则算出f（N）大概需要40秒的时间，计算时间会随着N的增大而线性增长。

看起来要计算从1到N的数字中所有1的和，至少也得遍历1到N之间所有的数字才能得到。那么能不能找到快一点的方法来解决这个问题呢？要提高效率，必须摈弃这种遍历1到N所有数字来计算f（N）的方法，而应采用另外的思路来解决这个问题。

**代码一**

/*---------------------------------------
    *   日期：2015-07-18
    *   作者：SJF0115
    *   题目: 233.Number of Digit One
    *   网址：https://leetcode.com/problems/number-of-digit-one/
    *   结果：超时
    *   来源：LeetCode
    *   博客：
    -----------------------------------------*/
    #include <iostream>
    #include <vector>
    using namespace std;
    
    class Solution {
    public:
        int countDigitOne(int n) {
            if(n <= 9 && n >= 1){
                return 1;
            }//if
            if(n <= 0){
                return 0;
            }//if
            int result = 1;
            for(int i = 10;i <= n;++i){
                result += DigitOne(i);
            }//for
            return result;
        }
    private:
        // 计算num中1的个数
        int DigitOne(int num){
            int result = 0;
            while(num){
                if(num % 10 == 1){
                    ++result;
                }//if
                num /= 10;
            }//while
            return result;
        }
    };
    
    int main(){
        Solution s;
        int n;
        while(cin>>n){
            cout<<s.countDigitOne(n)<<endl;
        }//while
        return 0;
    }

**思路二**

让我们来分析一下对于一个特定的N，如何得到一个规律来分析在每一位上所有出现1的可能性，并求和得到最后的f（N）。

先从一些简单的情况开始观察，看看能不能总结出什么规律。

先看1位数的情况。

如果N = 3，那么从1到3的所有数字：1、2、3，只有个位数字上可能出现1，而且只出现1次，进一步可以发现如果N是个位数，如果N>=1，那么f（N）都等于1，如果N=0，则f（N）为0。

再看2位数的情况。

如果N=13，那么从1到13的所有数字：1、2、3、4、5、6、7、8、9、10、11、12、13，个位和十位的数字上都可能有1，我们可以将它们分开来考虑，个位出现1的次数有两次：1和11，十位出现1的次数有4次：10、11、12和13，所以f（N）=2+4=6。要注意的是11这个数字在十位和个位都出现了1，但是11恰好在个位为1和十位为1中被计算了两次，所以不用特殊处理，是对的。再考虑N=23的情况，它和N=13有点不同，十位出现1的次数为10次，从10到19，个位出现1的次数为1、11和21，所以f（N）=3+10=13。通过对两位数进行分析，我们发现，个位数出现1的次数不仅和个位数字有关，还和十位数有关：如果N的个位数大于等于1，则个位出现1的次数为十位数的数字加1；如果N的个位数为0，则个位出现1的次数等于十位数的数字。而十位数上出现1的次数不仅和十位数有关，还和个位数有关：如果十位数字等于1，则十位数上出现1的次数为个位数的数字加1；如果十位数大于1，则十位数上出现1的次数为10。

> f(13) = 个位出现1的个数 + 十位出现1的个数 = 2 + 4 = 6；  
> f(23) = 个位出现1的个数 + 十位出现1的个数 = 3 + 10 = 13；  
> f(33) = 个位出现1的个数 + 十位出现1的个数 = 4 + 10 = 14；  
> .........  
> f(93) = 个位出现1的个数 + 十位出现1的个数 = 10 + 10 = 20；

接着分析3位数。

如果N = 123：

> 个位出现1的个数为13：1, 11, 21, …, 91, 101, 111, 121  
> 十位出现1的个数为20：10～19, 110～119  
> 百位出现1的个数为24：100～123

f（23）= 个位出现1的个数 + 十位出现1的个数 + 百位出现1的次数 = 13 + 20 + 24 = 57；

同理我们可以再分析4位数、5位数。读者朋友们可以写一写，总结一下各种情况有什么不同。

根据上面的一些尝试，下面我们推导出一般情况下，从N得到f（N）的计算方法：

假设N=abcde，这里a、b、c、d、e分别是十进制数N的各个数位上的数字。如果要计算百位上出现1的次数，它将会受到三个因素的影响：**百位上的数字，百位以下（低位）的数字，百位（更高位）以上的数字。**

**如果百位上的数字为0，则可以知道，百位上可能出现1的次数由更高位决定**，比如12 013，则可以知道百位出现1的情况可能是100～199，1 100～1 199，2 100～2 199，…，11 100~11 199，一共有1 200个。也就是由更高位数字（12）决定，并且等于**更高位数字（12）×当前位数（100）**。

**如果百位上的数字为1，则可以知道，百位上可能出现1的次数不仅受更高位影响，还受低位影响，也就是由更高位和低位共同决定。**例如对于12 113，受更高位影响，百位出现1的情况是100～199，1 100～1 199，2 100～2 199，…，11 100~11 199，一共1 200个，和上面第一种情况一样，等**于更高位数字（12）×当前位数（100）**。但是它还受低位影响，百位出现1的情况是12 100～12 113，一共14个，**等于低位数字（13）+1**。

**如果百位上数字大于1（即为2~9），则百位上可能出现1的次数也仅由更高位决定**，比如12 213，则百位出现1的可能性为：100～199，1 100～1 199，2 100～2 199，…，11 100～11 199，12 100～12 199，一共有1 300个，并且等于**更高位数字+1（12+1）×当前位数（100）**。

这个方法只要分析N就可以得到f（N），避开了从1到N的遍历，输入长度为Len的数字N的时间复杂度为**O（Len），即为O（ln（n）/ln（10）+1）**。在笔者的计算机上，计算N=100 000 000，相对于第一种方法的40秒时间，这种算法不到1毫秒就可以返回结果，速度至少提高了40 000倍。

**代码二**

/*---------------------------------------
    *   日期：2015-07-19
    *   作者：SJF0115
    *   题目: 233.Number of Digit One
    *   网址：https://leetcode.com/problems/number-of-digit-one/
    *   结果：AC
    *   来源：LeetCode
    *   博客：
    -----------------------------------------*/
    #include <iostream>
    #include <vector>
    using namespace std;
    
    class Solution {
    public:
        int countDigitOne(int n) {
            if(n == 0){
                return 0;
            }//if
            int result = 0;
            int lowerNum = 0,curNum = 0,highNum = 0;
            int base = 1;
            int num = n;
            while(num){
                // 低位部分
                lowerNum = n - num * base;
                // 当前部分
                curNum = num % 10;
                // 高位部分
                highNum = num / 10;
                // 如果为0则这一位1出现的次数由更高位决定 (更高位数字*当前位数)
                if(curNum == 0){
                    result += highNum * base;
                }//if
                // 如果为1则这一位1出现的次数不仅受更高位影响还受低位影响(更高位数字*当前位数+低位数字+1)
                else if(curNum == 1){
                    result += highNum * base + (lowerNum + 1);
                }//else
                // 大于1则仅受更高位影响((更高位数字+1)*当前位数)
                else{
                    result += (highNum + 1) * base;
                }//else
                num /= 10;
                base *= 10;
            }//while
            return result;
        }
    };
    
    int main(){
        Solution s;
        int n;
        while(cin>>n){
            cout<<s.countDigitOne(n)<<endl;
        }//while
        return 0;
    }

本文原文地址：[https://blog.csdn.net/SunnyYoona/article/details/46943643][https_blog.csdn.net_SunnyYoona_article_details_46943643]

[https_blog.csdn.net_SunnyYoona_article_details_46943643]: https://blog.csdn.net/SunnyYoona/article/details/46943643