当前位置: 首页 > news >正文

《计算机算法设计与分析》系列--算法实现题1.1-统计数字问题

引言:
这个题在原书的配套习题解答中,描述得比较简略,我不太看得懂,于是按自己的思路做了一遍。

问题描述:
一本书有n页,页码为1,2,.. N,(注意,页码的格式,0不会在最前面)
问在这所有的页码中,0-9这10个数字,分别有多少个?
比如11页的书,

数字 0 1 2 3 4 5 6 7 8 9
次数 1 4 1 1 1 1 1 1 1 1

分析:
1、穷举法,for(i=1; i<=n; i++) 分解每一个页码,然后统计,可以得到结果,但时间复杂度太高,为nlogn,显然不是我们理想中的答案。

2、
以n=3267,m=4(位)为例,如果页码是从第0页开始,且格式是:0000,0001,0002,3266,3267

如果是数字1:
在第1位(千位)的次数是:1000个(1000-1999)
在第2位(百位)的次数是:,400个,(0100-0199,1100-1199,2100-2199,3100-3199)
即千位的0-3共4个,4100=400;
在第3位的次数是:,330个(0010-0019,3210-3219);即千位和百位00-32共33个,33
10=330;
在第4位上的次数是:000-326共327个;
所以1的个数为:1000+400+330+327=2057个;

如果是3:
在第1位的次数是:268,是的,就是后面几位;
在第2位的次数是:(0300-0399,1300-1399,2300-2399,0),300个;
在第3位的次数是:00-32共33个,330个
在第4位的次数是:0003--3263,327个,
所以3的个数为:267+300+330+327=1224个;

如果是6:
在第1位的次数:0
在第2位的次数:0600-0699,1600-1699,2600-2699,300个
在第3位的次数是:(0060-0069)--(3160--3169) 320个, 3260-3267,8个
在第4位的次数是:0006--3266,共327个;
300+320+8+327=955个;

总结:
把数字n存放在数组中,a[4]={3,2,6,7},把数字0-9和此数组每一位依次比对。
如果小于,cnt = (n/10(m-i)+1)*10(m-i-1)
如果等于,cnt = n/10^(m-i) * 10^(m-i-1) + n%(10^(m-i-1)) + 1;
如果大于:cnt = n/(10^(m-i)) * 10^(m-i-1)

代码如下:
sx1.1

这个复杂度为logn,比较满意。
好久没写代码了,有点手生。

http://www.hskmm.com/?act=detail&tid=16241

相关文章:

  • 银河麒麟系统root密码重置
  • 银河麒麟系统磁盘管理
  • 浅谈傅里叶级数
  • js遍历对象
  • day 10 (函数2 )
  • 入驻了爱发电
  • 奖励函数(双足)
  • 离线部署镜像仓库搭建
  • Temporal和Airflow有什么差别
  • lc1035-不相交的线
  • 自我介绍与未来规划
  • 解构React Server Components:服务端序列化与流式传输的底层逻辑
  • js里面的单引号、双引号及反引号的用法
  • 牛客刷题-Day4
  • Skinned Mesh Renderer与LOD系统蒙皮变形异常全解析
  • K8S (Containerd)初始化安装流程
  • ?模拟赛 赛后总结
  • 日志|动态规划|最长回文子串|最长公共子序列|HTML CSS
  • Java 字段命名避坑: success和isSuccess
  • OTA升级时软件异常复位问题分析
  • Atcoder Educational DP Contest 做题记录
  • 20250924
  • 跨端边云时序数据管理新范式:Apache IoTDB 的 DB+AI 融合之道 - 实践
  • 《Real-Time Rendering》第二章 图形渲染管线
  • 放弃Unity后,我为什么选择了Unigine?
  • PHP 与 Java 的终极对比:2025年,开发者该如何选择? - 详解
  • 题单63——流程控制
  • 银行同业存单的信用等级
  • 软件技术基础第一次作业
  • 2025XDOJ个人题解——写在前面