题目描述
求出113的整数中1出现的次数,并算出1001300的整数中1出现的次数？为此他特别数了一下1~13中包含1的数字有1、10、11、12、13因此共出现6次,但是对于后面问题他就没辙了。ACMer希望你们帮帮他,并把问题更加普遍化,可以很快的求出任意非负整数区间中1出现的次数（从1 到 n 中1出现的次数）。
思路一
依次统计1-n每个数中1的个数，然后依次累加得到最后1出现的总次数
public int NumberOf1ToI(int i){
int countOfI = 0;
while(i > 0){//注意这里不能等于0，否则就是一个死循环了，0/10永远等于0
int rem = i % 10;
if(rem == 1) countOfI++;
i = i / 10;
}
return countOfI;
}
public int NumberOf1Between1AndN_Solution(int n) {
int count = 0;
for(int i = 1; i <= n; i++){
count += NumberOf1ToI(i);
}
return count;
}
时间复杂度：
对于数字n有o(lgn)位，而我们需要判断每一位数字是不是1
从1-n那么总共的时间复杂度就是o(nlogn)
思路二
举例发现其中的规律
-
n为一位数：n ={1,2,3…9}；1出现的次数只能为1
-
n为两位数：
- n =13 ;那么1出现的次数 = 个位出现1 + 十位出现1 ={1，11}+{10，11，12，13} = 2 + 4 = 6=2+(3+1)=>当十位数字<1时，次数和个位数字的大小有关
- n = 15;1出现的次数 = 个位出现1 + 十位出现1={1,11}+{10,11,12,13,14,15}=2+6=8=2+(5+1)=>(3+1)=>当十位数字<1时，次数和个位数字的大小有关
- n=23;1出现的次数=个位出现1 + 十位出现1={1，11，21}+{10，11，12，13，4，15，16，17，18，19}=3 + 10 = 13 = (2+1) +10=>当十位数字>1时，次数和十位数字的大小有关
- n = 45;1出现的次数=个位出现1 + 十位出现1={1,11,21,31,41}+{10，11，12，13，4，15，16，17，18，19}=5+10=15=(4+1)+10=>当十位数字>1时，次数和十位数字的大小有关
-
n为三位数：
- n=123;1出现的次数 = 个位出现1 + 十位出现1 +百位出现1={1，11，21，31，41，51，61，71，81，91，101，111，121}+{10-19，110-119}+{100-123}=13+20+24=57
总结规律：
假设N = abcde（a,b,c,d,e分别代表个位，十位，百位。。。上的数字）
那么同样根据上面的推理：
1出现的次数 = 个位出现1的次数 + 十位出现1 的次数+百位出现1的次数+千位出现1的次数+万位出现1的次数
这里以百位出现1的次数为例:
- c = 0： 百位出现1的次数 = highNumber * 100 =ab * 100
- c = 1: 百位出现1的次数=highNumber * 100 + lowNumber+1
- c>1: 百位出现1的次数=(highNumber+1) * 100
举例：
-
c=0: N = 12013 百位出现1的次数 = {100-199，1100-1199，2100-2199，3100-3199，。。。9100-999，10100-10199, 11100-11199}=12 * 100 =1200 = highNumber * 100
-
c=1：N=12113 百位出现1的次数= {100-199，1100-1199，2100-2199，3100-3199，。。。9100-999，10100-10199, 11100-11199} + {12100-12113} = {N = 12013时百位出现1的次数} + {12100-12113 } = 1200 + 114 = 12 * 100 + 113 +1 = highNumber * 100 + lowNumber+1
-
c>1:N=12213 百位出现1的次数= {100-199，1100-1199，2100-2199，3100-3199，。。。9100-999，10100-10199, 11100-11199,12100-12199} = 13 * 100 = (12 + 1) * 100 = (highNumber+1) * 100
时间复杂度：o(logn)
public int NumberOf1Between1AndN_Solution(int n) {
int count = 0;//1的个数
int i = 1;//轮询代表（个位->十位->百位->千位。。。。）
int current = 0,lowNumber = 0,highNumber = 0;
//注意终止条件
while((n/i)!= 0){
current = (n/i)%10; //当前位数字
System.out.println("当前位current："+current);
highNumber = n/(i*10); //高位数字
System.out.println("高位数字highNumber："+highNumber);
//注意低位如何表示
lowNumber = n-(n/i)*i; //低位数字
System.out.println("低位数字lowNumber："+lowNumber);
//如果为0,出现1的次数由高位决定,等于高位数字 * 当前位数
if (current == 0)
count += highNumber*i;
//如果为1,出现1的次数由高位和低位决定,高位*当前位+低位+1
else if(current == 1)
count += highNumber * i + lowNumber + 1;
//如果大于1,出现1的次数由高位决定,//（高位数字+1）* 当前位数
else{
count += (highNumber + 1) * i;
}
//前移一位
i = i*10;
}
return count;
}
21345
当前位current：5
高位数字highNumber：2134
低位数字lowNumber：0
当前位current：4
高位数字highNumber：213
低位数字lowNumber：5
当前位current：3
高位数字highNumber：21
低位数字lowNumber：45
当前位current：1
高位数字highNumber：2
低位数字lowNumber：345
当前位current：2
高位数字highNumber：0
低位数字lowNumber：1345
18821
参考
剑指offer-整数中1出现的次数（从1到n整数中1出现的次数）
[剑指offer三十一之连数中1出现的次数（从1到n整数中1出现的次数]