关于统计数字问题的算法
作者:jcwKyl 发布时间:2023-11-03 00:33:32
一本书的页码从自然数1开始顺序编码直到自然数n。书的页码按照通常的习惯编排,每个页码都不含多余的前导数字0。例如第6页用6表示而不是06或006。数字统计问题要求对给定书的总页码,计算出书的全部页码中分别用到多少次数字0,1,2,3,.....9。
这个题目有个最容易想到的n*log10(n)的算法。这是自己写的复杂度为O(n*log10(n))的代码:
void statNumber(int n) {
int i, t;
int count[10] = {0};
for(i = 1; i <= n; i++) {
t = i;
while(t) {
count[t%10]++;
t/=10;
}
}
for(i = 0; i < 10; i++) {
printf("%d/n", count[i]);
}
}
仔细考虑m个n位十进制数的特点,在一个n位十进制数的由低到高的第i个数位上,总是连续出现10^i个0,然后是10^i个1……一直到10^i个9,9之后又是连续的10^i个0,这样循环出现。找到这个规律,就可以在常数时间内算出第i个数位上每个数字出现的次数。而在第i个数位上,最前面的10^i个0是前导0,应该把它们减掉。
这样,可以只分析给定的输入整数n的每个数位,从面可以得到一个log10(n)的算法,代码如下:
void statNumber(int n) {
int m, i, j, k, t, x, len = log10(n);
char d[16];
int pow10[12] = {1}, count[10] = {0};
for(i = 1; i < 12; i++) {
pow10[i] = pow10[i-1] * 10;
}
sprintf(d, "%d", n);
m = n+1;
for(i = 0; i <= len; i++) {
x = d[i] - '0';
t = (m-1) / pow10[len-i];
count[x] += m - t * pow10[len-i];
t /= 10;
j = 0;
while(j <= x-1) {
count[j] += (t + 1) * pow10[len-i];
j++;
}
while(j < 10) {
count[j] += t * pow10[len - i];
j++;
}
count[0] -= pow10[len-i]; /* 第i个数位上前10^i个0是无意义的 */
}
for(j = 0; j < 10; j++) {
printf("%d/n", count[j]);
}
}
通过对随机生成的测试数据的比较,可以验证第二段代码是正确的。
对两段代码做效率测试,第一次随机产生20万个整数,结果在我的电脑上,第二段代码执行1.744秒。第一段代码等我吃完钣回来看还是没反应,就强行关了它。
第二次产生了1000个整数,再次测试,结果第一段代码在我的电脑上执行的时间是
10.1440秒,而第二段代码的执行时间是0.0800秒。
其原因是第一段代码时间复杂度为O(n*log10(n)),对m个输入整数进行计算,则需要的时间为 1*log10(1) + 2*log10(2) + ... + m*log10(m),当n > 10时,有n*log10(n) > n,所以上式的下界为11+12+....+m,其渐近界为m*m。对于20万个测试数据,其运行时间的下界就是4*10^10。
同样可得第二段代码对于n个输入数据的运行时间界是n*log10(n)的。
上面的代码中有个pow10数组用来记录10^i,但10^10左右就已经超过了2^32,但是题目给定的输入整数的范围在10^9以内,所以没有影响。
原著中给出的分析如下:
考察由0,1,2...9组成的所有n位数。从n个0到n个9共有10^n个n位数。在这10^n个n位数中,0,1,2.....9第个数字使用次数相同,设为f(n)。f(n)满足如下递推式:
n>1:
f(n) = 10f(n-1)+10^(n-1)
n = 1:
f(n) =1
由此可知,f(n) = n*10^(n-1)。
据此,可从高位向低位进行统计,再减去多余的0的个数即可。
著者的思想说的更清楚些应该是这样:
对于一个m位整数,我们可以把0到n之间的n+1个整数从小到大这样来排列:
000......0
.............
199......9
200......0
299......9
.........
这样一直排到自然数n。对于从0到199......9这个区间来说,抛去最高位的数字不看,其低m-1位恰好就是m-1个0到m-1个9共10^(m-1)个数。利用原著中的递推公式,在这个区间里,每个数字出现的次数(不包括最高位数字)为(m-1)*10^(m-2)。假设n的最高位数字是x,那么在n之间上述所说的区间共有x个。那么每个数字出现的次数x倍就可以统计完这些区间。再看最高位数字的情况,显然0到x-1这些数字在最高位上再现的次数为10^(m-1),因为一个区间长度为10^(m-1)。而x在最高位上出现次数就是n%10^(m-1)+1了。接下来对n%10^(m-1),即n去掉最高位后的那个数字再继续重复上面的方法。直到个位,就可以完成题目要求了。
比如,对于一个数字34567,我们可以这样来计算从1到34567之间所有数字中每个数字出现的次数:
从0到9999,这个区间的每个数字的出现次数可以使用原著中给出的递推公式,即每个数字出现4000次。
从10000到19999,中间除去万位的1不算,又是一个从0000到9999的排列,这样的话,从0到34567之间的这样的区间共有3个。所以从00000到29999之间除万位外每个数字出现次数为3*4000次。然后再统计万位数字,每个区间长度为10000,所以0,1,2在万位上各出现10000次。而3则出现4567+1=4568次。
之后,抛掉万位数字,对于4567,再使用上面的方法计算,一直计算到个位即可。
下面是自己的实现代码:
void statNumber_iterative(int n) {
int len, i, k, h, m;
int count[10] = {0};
int pow10[12] = {1,10,100,1000,10000,100000,1000000,10000000,100000000,1000000000};
char d[16];
len = log10(n); /* len表示当前数字的位权 */
m = len;
sprintf(d, "%d", n);
k = 0; /* k记录当前最高位数字在d数组中的下标 */
h = d[k] - '0'; /* h表示当前最高位的数字 */
n %= pow10[len]; /* 去掉n的最高位 */
while(len > 0) {
if(h == 0) {
count[0] += n + 1;
h = d[++k] - '0';
--len;
n %= pow10[len];
continue;
}
for(i = 0; i < 10; i++) {
count[i] += h * len * pow10[len-1];
}
for(i = 0; i < h; i++) {
count[i] += pow10[len];
}
count[h] += n + 1;
--len;
h = d[++k] - '0';
n %= pow10[len];
}
for(i = 0; i <= h; i++) {
count[i] += 1;
}
/* 减去前导0的个数 */
for(i = 0; i <= m; i++) {
count[0] -= pow10[i];
}
for(i = 0; i < 10; i++) {
printf("%d/n", count[i]);
}
}
猜你喜欢
- 只能输入数字:"^[0-9]*$"。只能输入n位的数字:"^\d{n}$"。只能输入至少n位的数字:
- 现如今打开一个 App,比如头条、微博,都会有长列表,随着我们不断地滑动,视窗内的内容也会不断地更新。今天就用 Flutter 实现一下这种
- 面试题1:说一下抽象类和接口有哪些区别?正经回答:抽象类和接口的主要区别:从设计层面来说,抽象类是对类的抽象,是一种模板设计;接口是行为的抽
- 服务降级服务压力剧增的时候,根据当前的业务情况及流量对一些服务和页面有策略的降级,以此缓解服务器的压力,以保证核心任务的进行。同时保证部分甚
- maven配置项目的jdk版本无效排查最近在配置项目的jdk的时候发现在pom.xml中配置的1.8版本无效,maven更新后就变成了1.7
- 这篇文章主要介绍了java property配置文件管理工具框架过程详解,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考
- 为什么要写这篇文章经过了若干年的发展,Java逐步从java8升级为java11,java17。让我们对比学习一下最新一版的LTS版本和ja
- Pom依赖<parent> <groupId>org.springframework.bo
- 官网教程一、翻转(镜像)头文件 quick_opencv.h:声明类与公共函数#pragma once#include <opencv
- 该工具包含是封装了jedis,包含redis.properties和jedisPool,序列化使用的是protostuff,map类型操作使
- 我就废话不多说了,大家还是直接看代码吧~<?xml version="1.0" encoding="UT
- Java NIO(New IO)是Java 1.4版本中引入的一套全新的IO处理机制,与之前的传统IO相比,NIO具有更高的可扩展性和灵活性
- 首先引入pom <!--SpringBoot 2.1.0--> <parent>  
- 静态代理: 由我们开发者自己手动创建或者在程序运行前就已经存在的代理类,静态代理通常只代理一个类, * 是代理一个接口下的多个实现类。动态
- 系列文章已完成,目录如下:jdk-logging log4j logback日志系统实现机制原理介绍commons-lo
- 背景实际开发中,常常需要将比较复杂的 JSON 字符串转换为对应的 Java 对象。这里记录下解决方案。如下所示,是入侵事件检测得到的 JS
- 接触过Android开发的同学们都知道在Android中访问程序资源基本都是通过资源ID来访问。这样开发起来很简单,并且可以不去考虑各种分辨
- File类概述File类能新建、删除、重命名文件和目录,但不能访问文件内容本身,如果需要访问文件内容本身,则需要使用后续的输入/输出流。要在
- 前言:List 去重指的是将 List 中的重复元素删除掉的过程。此题目考察的是对 List 迭代器、Set 集合和 JDK 8 中新特性的
- static修饰符是java里面非常常用的一个东西,用法也非常多。然而,在kotlin里竟然没有这个东西!那该如何替代呢?本文就总结了下ja