首页 > 代码库 > 整数中1出现的次数（从1到n整数中1出现的次数）
整数中1出现的次数（从1到n整数中1出现的次数）
题目：求出1~13的整数中1出现的次数,并算出100~1300的整数中1出现的次数？为此他特别数了一下1~13中包含1的数字有1、10、11、12、13因此共出现6次,但是对于后面问题他就没辙了。ACMer希望你们帮帮他,并把问题更加普遍化,可以很快的求出任意非负整数区间中1出现的次数。
见到这道题的第一反应可能是我可以先计算1~n每个数中1出现的次数，然后把所有结果相加即可。此时，时间复杂度为O(n*log(n)).
接下来是一种时间复杂度为O(log(n))的解法（这里以一个具体的例子来进行说明）：n=2234
1.将2234分为1~234，235~2234两段；
2.计算235~2234数字中出现1的次数。首先，出现在最高位上出现的次数。这里最高位为千位，由于最高位大于1,从1000~1999中，1一共出现103次；若最高位等于1，则1在最高位出现的次数为除去最高数字之后剩下的数字加1。其次，计算除去最高位外剩余位上出现的1.这里可以再将区间进行划分：235~1234和1235~2234.每段上出现1的次数是相同的：除去最高位剩余3位，选择其中一位是1，其余两位可以在0~9这10个数字中任意选择，所以每段出现的次数为3*102。最后，综合上述两步，在235~2234数字中出现1的次数为103+2*3*102；
3.递归采用步骤1,2计算1~234中出现1的次数。
1 public class Num31_NumberOf1Between1AndN { 2 3 public int NumberOf1Between1AndN_Solution(int n) { 4 int res = 0,len=1,num=n; 5 while((num/10)!=0){ 6 len++; 7 num = num/10; 8 }//求出是几位数 9 res = doSum(n,len);10 return res;11 }12 public int doSum(int end,int len) {13 //若为1~0或者长度为0，直接返回014 if(end == 0||len==0)return 0;15 //只剩一位的情况16 if(len == 1 && end ==0)return 0;17 if(len == 1 && end > 0)return 1;18 19 int high,rest;20 int pow = (int)Math.pow(10, len-1);//10^(len-1)21 int mul = end/pow;//最高位22 //求最高位上1的个数23 if(mul==1) 24 high = end-pow+1;25 else high = pow;26 rest = mul * (len-1)*(pow/10);//除最高位以外，剩余位出现1的个数27 //和的前两项为（end%pow+1 ~ end）中1出现的次数28 //和的最后一项(1 ~ end%pow)中1的出现的次数29 return high + rest +doSum(end-mul*pow,len-1);30 } 31 }
整数中1出现的次数（从1到n整数中1出现的次数）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。