面试题32:从1到n整数中1出现的次数
题目
输入一个正整数n,求从1到n这n个整数的十进制表示中1出现的次数。例如输入12,从1到12这些整数中包含1的数字有1,10,11和12。1一共出现了5次。
暴力算法
遍历从1到n的数,对每一个数进行解析,每个数的解析时间是。
算法时间复杂度是
public int NumberOf1Between1AndN_Solution(int n) {
int sum = 0;
for(int i=1;i<=n;i++){
sum+=countOne(i);
}
return sum;
}
private int countOne(int n){
int count = 0;
while(n!=0){
int a = n%10;
if(a==1){
count++;
}
n/=10;
}
return count;
}
剑指offer上的解法
以n=21345
为例,如果我们能把问题分解为:分别求出1~1345
和1346~21345
的解,然后实际只去求1346~21345
,而对于求1~1345
使用递归,那么问题就解决了。
如何求1346~21345
的解呢?
我们将分类讨论,最高位1出现多少次?其余位1出现多少次?
最高位1出现在10000~19999
中,总共10000个,但这不是一般情况,如果是10000~11345
呢?(如果n=11345
),所以这里要分类讨论一下,如果最高位小于2,那么总共出现1的数应该就是后面所有的数再加1,也就是1345+1(加1是因为从0算起)。剩余4位中比如千位是1,然后其它3位随便是什么,这样就有个,4位就是:,然后最高位还可以分别是1和2,所以总共是:个。抽象成一般原理:
因为只跟n的位数有关,所以算法时间复杂度是:
public int NumberOf1Between1AndN_Solution(int n) {
String s = Integer.toString(n);
char[] c = s.toCharArray();
return recurse(c, 0);
}
private int power10(int n){
int result = 1;
for(int i=0;i<n;i++){
result*=10;
}
return result;
}
private int recurse(char[] c, int i){
if(i==c.length-1){
return 1;
}
int sum = 0;
// 最高位1的个数
if(c[i]>'1'){
sum += power10(c.length-1-i);
}else{
sum += charToInt(c, i+1)+1;
}
// 其余位1的个数
sum += (c[i]-'0')*(c.length-1-i)*power10(c.length-2-i);
return sum+recurse(c, i+1);
}
private int charToInt(char[] c, int index){
int temp = 0;
for(int j=index;j<c.length;j++){
temp *= 10;
temp += (c[j]-'0');
}
return temp;
}
编程之美上的解法
如果我们发现了一个规律:
1到10,个位数是1的个数是:1
1到100,十位数是1的个数是:10
1到1000,百位数是1的个数是:100
以此类推
依旧以21345为例。
先统计其中个位商上现1的个数:21340是10的2134倍,也就意味着以10为周期1会不断的在个位上出现2134次,再加上21341到21345中出现的21341这个也是个位出现1,所以总共是2135个个位1。
然后统计十位上出现1的个数:21300是100的213倍,以100为周期,十位每次出现10个1,也就是213*10
,再加上从21301到21345,中2131x,这些10个数,总共是213*10+10
其实规律这就已经出来了,写成代码如下:
public int NumberOf1Between1AndN_Solution(int n) {
int sum = 0;
int count = 10;
while(n*10/count!=0){
int a = n/count;
int b = n%count;
if(b>(2*count/10)){
b = (count/10);
}else if(b>=(count/10)){
b = n%(count/10)+1;
}else{
b = 0;
}
sum += a*count/10+b;
count*=10;
}
return sum;
}
算法复杂度也很容易得到:
网友评论