博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
一道算法题-从1到n整数中1出现的次数
阅读量:6895 次
发布时间:2019-06-27

本文共 2193 字,大约阅读时间需要 7 分钟。

1. 题目描述

输入一个整数n,求从1到n这n个整数的十进制表示中1出现的次数。例如输入12,从1到12这些整数中包含1的数字有1,10,11和12,1一共出现了5次。

2. 题目来源

第一次看到是在《剑指Offer》第2版上,面试题32。和上都有这道题。

3. 本文的目的

看了《剑指Offer》上的解法,我觉得不能算好:

  1. 这段解释描述有些不清晰,而且没有图,难以理解。
  2. 从书中给出的实现上来看,显得有些凌乱。

在这篇博客里,会给出一个我对这道题的解法,包括完整的解题思路,完整代码,时间复杂度分析。

4. 解题思路

考虑将n的十进制的每一位单独拿出讨论,每一位的值记为weight。

1)个位

从1到n,每增加1,weight就会加1,当weight加到9时,再加1又会回到0重新开始。那么weight从0-9的这种周期会出现多少次呢?这取决于n的高位是多少,看图: 

这里写图片描述

以534为例,在从1增长到n的过程中,534的个位从0-9变化了53次,记为round。每一轮变化中,1在个位出现一次,所以一共出现了53次。 
再来看weight的值。weight为4,大于0,说明第54轮变化是从0-4,1又出现了1次。我们记1出现的次数为count,所以: 

count = round+1 = 53 + 1 = 54

如果此时weight为0(n=530),说明第54轮到0就停止了,那么: 

count = round = 53

 

2) 十位

对于10位来说,其0-9周期的出现次数与个位的统计方式是相同的,见图: 

这里写图片描述

不同点在于:从1到n,每增加10,十位的weight才会增加1,所以,一轮0-9周期内,1会出现10次。即rount*10。 
再来看weight的值。当此时weight为3,大于1,说明第6轮出现了10次1,则: 

count = round*10+10 = 5*10+10 = 60

如果此时weight的值等于0(n=504),说明第6轮到0就停止了,所以: 

count = round*10+10 = 5*10 = 50

如果此时weight的值等于1(n=514),那么第6轮中1出现了多少次呢?很明显,这与个位数的值有关,个位数为k,第6轮中1就出现了k+1次(0-k)。我们记个位数为former,则: 

count = round*10+former +1= 5*10+4 = 55

 

3) 更高位

更高位的计算方式其实与十位是一致的,不再阐述。

4) 总结

将n的各个位分为两类:个位与其它位。 

对个位来说:

  • 若个位大于0,1出现的次数为round*1+1
  • 若个位等于0,1出现的次数为round*1

对其它位来说,记每一位的权值为base,位值为weight,该位之前的数是former,举例如图: 

这里写图片描述

则:

 

  • 若weight为0,则1出现次数为round*base
  • 若weight为1,则1出现次数为round*base+former+1
  • 若weight大于1,则1出现次数为rount*base+base

比如:

  • 534 = (个位1出现次数)+(十位1出现次数)+(百位1出现次数)=(53*1+1)+(5*10+10)+(0*100+100)= 214
  • 530 = (53*1)+(5*10+10)+(0*100+100) = 213
  • 504 = (50*1+1)+(5*10)+(0*100+100) = 201
  • 514 = (51*1+1)+(5*10+4+1)+(0*100+100) = 207
  • 10 = (1*1)+(0*10+0+1) = 2

5. 完整代码

1 int NumberOf1Between1AndN_Solution(int n) 2     { 3         if(n<1) 4             return 0; 5         int count = 0; 6         int base = 1; 7         int round = n; 8         while(round>0) 9         {10             int weight = round%10;11             round/=10;12             count += round*base;13             if(weight==1)14                     count+=(n%base)+1;15             else if(weight>1)16                 count+=base;17             base*=10;18         }19     return count;20     }
 

6. 时间复杂度分析

由分析思路或者代码都可以看出,while循环的次数就是n的位数,logn(以10为底),而循环体内执行的操作都是有限次的,所以时间复杂度为O(logn)

 

参考文献:http://blog.csdn.net/yi_afly/article/details/52012593

转载于:https://www.cnblogs.com/smile233/p/8338361.html

你可能感兴趣的文章
vs2017莫名自动退出调试状态可以尝试一下如下的方法
查看>>
Adaptive Execution让Spark SQL更高效更好用
查看>>
快手服务治理平台KESS的设计理念和实战
查看>>
微软发布Azure Cosmos DB产品以及新的物联网解决方案
查看>>
与Bob McWhirter的问答:WildFly Swarm更名为Thorntail项目
查看>>
Java 11正式发布,新特性解读
查看>>
《Fit for Purpose》作者访谈录
查看>>
与Brian Goetz聊Java的数据类
查看>>
Emoji 上的 Swift:换一种视角来理解 Swift 高阶函数
查看>>
区块链将颠覆游戏业,游戏内商品未来也可带出游戏、自由交易
查看>>
Linux/Mac安装oh-my-zsh后不执行~/.bash_profile、~/.bashrc解决办法
查看>>
安卓开发_深入理解广播机制
查看>>
技术大咖云集,GIAC 2017全球互联网架构大会圆满落幕
查看>>
php取整函数ceil,floor,round,intval函数的区别
查看>>
elk5.x环境搭建与常用插件安装
查看>>
MySQL大表删除导致服务器变慢的分析
查看>>
windows server操作系统一定要关闭开机磁盘自检
查看>>
Java解析Excel文件
查看>>
MySQL数据类型简介
查看>>
由于未预料的错误,现在无法使用nautilus
查看>>