整数中1出现的次数整数中1出现的次数（从1到n整数中1出现的次数）

83 阅读 0 评论 55 点赞

我是靠谱客的博主隐形电脑，这篇文章主要介绍整数中1出现的次数整数中1出现的次数（从1到n整数中1出现的次数），现在分享给大家，希望可以做个参考。

最近刷题遇到一道题感觉解法挺妙的，跟大家分享一下。希望对大家能够有所帮助。

整数中1出现的次数（从1到n整数中1出现的次数）

本题考点： 基础数学牛客链接
题目描述
输入一个整数 n ，求 1～n 这 n 个整数的十进制表示中 1 出现的次数
例如， 1~13 中包含 1 的数字有 1 、 10 、 11 、 12 、 13 因此共出现 6 次

注意：11 这种情况算两次

数据范围：1≤n≤30000
进阶：空间复杂度 O(1) ，时间复杂度 O(lognn)

解题思路：
题中说要找1出现的次数，最简单的方法想必大家也都能想到。把 1~ N 中每一个数字的每一位都和1进行比较进行累加。不过这样时间复杂度为O(n * log(n))效率太低了我们不用这种方法。因此我们就需要找1在数字中出现的规律了。为了找到规律我们不防用一个稍微大一点的数字如25733来进行分析。如图：
在这里插入图片描述

代码：

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
public:
    int NumberOf1Between1AndN_Solution(int n) {
        if(n <= 0)
            return 0;
        string strN = to_string(n);
        return NumberOf1(strN.c_str());
    }
    int NumberOf1(const char* strN)
    {
        size_t length = strlen(strN);
        int first = *strN - '0';

        //递归返回条件
        if(!strN || *strN < 0 || * strN > '9' || *strN == '')
            return 0;
        if(length == 1 && first == 0)
            return 0;
        if(length == 1 && first > 0)
            return 1;

        //最高位出现1的次数
        int NumFirstDigit = 0;
        if(first > 1)
            NumFirstDigit = pow(10, length - 1);

        else if(first == 1)
            NumFirstDigit = atoi(strN + 1) + 1;
        //其他位出现1的次数
        int NumOtherDigits = pow(10, length - 2) * (length - 1) * first;

        //递归处理剩余数
        int NumRecurSize = NumberOf1(strN + 1);

        return NumFirstDigit + NumOtherDigits + NumRecurSize;
    }
}