算法：1～n 整数中 1 出现的次数

Myth丶恋晨 2024-04-01 16:16 25阅读 0赞

![b3836acb38f930ca614b1f50a7472e0a.jpeg][]

输入一个整数 n ，求1～n这n个整数的十进制表示中1出现的次数。

例如，输入12，1～12这些整数中包含1 的数字有1、10、11和12，1一共出现了5次。

## 示例 ##

*  输入：n = 12
 *  输出：5

## 限制 ##

*  1 <= n < 2^31

## 方法：枚举 ##

*  当 cur = 0 时，此位 1 的个数的计算公式为：high \* digit；
 *  当 cur = 1 时，此位 1 的个数的计算公式为：high \* digit + low + 1；
 *  当 cur > 1 时，此位 1 的个数的计算公式为：(high +1) \* digit。

**代码如下：**

![b43795c17983ffdf4288273ebc688e26.jpeg][]

## 复杂度分析 ##

*  时间复杂度 ： O(logn) 。
 *  空间复杂度 ： O(1) ，几个变量使用常数大小的额外空间。

## END ##

聪明出于勤奋，天才在于积累，赠友人。

好兄弟可以点赞并关注我的公众号“javaAnswer”，全部都是干货。

![58682672f7ba4d3cb12373436358fe1b.png][]

[b3836acb38f930ca614b1f50a7472e0a.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/3b9135c2ad004aca9b623ed98184c412.jpeg
[b43795c17983ffdf4288273ebc688e26.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/3f72514409594b2b82ec19899bce9f67.jpeg
[58682672f7ba4d3cb12373436358fe1b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/3caf727dd813479283bbe9ffba472333.png

发表评论取消回复

表情：

评论列表（有 0 条评论，25人围观）

还没有评论，来说两句吧...

相关阅读

相关算法：1～n 整数中 1 出现的次数

![b3836acb38f930ca614b1f50a7472e0a.jpeg][] 输入一个整数 n ，求1～n这n个整数的十进制表示中1出现的次数。例如，输入12，1

Myth丶恋晨/ 2024年04月01日 16:16/ 0 赞/ 26 阅读

相关 49：1~n整数中1出现的次数

1~n整数中1出现的次数输入一个整数n，求1~n这n整数的十进制表示中1出现的次数。主要还是一个找规律的题目。 [解题思路传送门][Link 1] pub

Bertha 。/ 2022年11月27日 00:54/ 0 赞/ 107 阅读

相关剑指offer----整数中1出现的次数（从1到n整数中1出现的次数）

设N = abcde ,其中abcde分别为十进制中各位上的数字。如果要计算百位上1出现的次数，它要受到3方面的影响：百位上的数字，百位以下（低位）的数字，百位以上（高位

深碍√TFBOYSˉ_/ 2022年09月26日 11:54/ 0 赞/ 127 阅读

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

链接： [https://www.nowcoder.com/questionTerminal/bd7f978302044eee894445e244c7eee6][https_w

女爷i/ 2022年06月06日 03:57/ 0 赞/ 222 阅读

相关剑指Offer | 整数中1出现的次数（从1到n整数中1出现的次数）

做了个剑指Offer的题目目录，链接如下： [https://blog.csdn.net/mengmengdastyle/article/details/80317246]

港控/mmm°/ 2022年05月23日 04:34/ 0 赞/ 183 阅读

相关从1到n的整数中1出现的次数

在<编程之美>和<剑指offer>上都有这么一道题目，那就是求从1到n的整数中1出现的次数。这两本书中都给出了两种算法，本人觉得<编程之美>上的算法更胜一筹。现将两种算法实

骑猪看日落/ 2022年03月14日 16:50/ 0 赞/ 170 阅读

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

时间限制：1秒空间限制：32768K 热度指数：151197 算法知识视频讲解题目描述求出113的整数中1出现的次数,并算出1001300的整数中1出现的次数

末蓝、/ 2022年03月09日 10:49/ 0 赞/ 212 阅读

相关剑指Offer-整数中1出现的次数（从1到n整数中1出现的次数）

题目描述求出1~ 13的整数中1出现的次数,并算出100~ 1300的整数中1出现的次数？为此他特别数了一下1~13中包含1的数字有1、10、11、12、13因此共出现

深藏阁楼爱情的钟/ 2022年02月20日 00:51/ 0 赞/ 245 阅读

相关剑指offer|整数中1出现的次数（从1到n整数中1出现的次数）

【题目描述】求出1-13的整数中1出现的次数,并算出100-1300的整数中1出现的次数？为此他特别数了一下1~13中包含1的数字有1、10、11、12、13因此共出现6

待我称王封你为后i/ 2022年01月28日 05:21/ 0 赞/ 254 阅读

相关剑指offer：整数中1出现的次数（从1到n整数中1出现的次数）

试题：求出1~13的整数中1出现的次数,并算出100~1300的整数中1出现的次数？为此他特别数了一下1~13中包含1的数字有1、10、11、12、13因此共出现6次,但

Myth丶恋晨/ 2021年06月24日 16:09/ 0 赞/ 395 阅读