你的位置:首页 > Java教程

[Java教程]微软算法100题30 在从1到n的整数中1出现的次数

30. 在从1到n的整数中1出现的次数
题目:输入一个整数n,求从1到n 这n个整数的十进制表示中1出现的次数。
例如输入12,从1到12这些整数中包含1的数字有1,10,11 和12,1 一共出现了5 次。
分析:这是一道广为流传的google 面试题

 

思路:

第一反应是遍历这N个数,然后对每个正数n不断用10取余来求各个位上1的次数,同理对每个数求1出现的次数并累加,但这种方法的时间复杂度是o(n),当n值很高时耗时太久

第二个思路是能不能通过数学的方法找到n上所有1的次数 (自己实在是想不出来,先从网上搜了一下,最后发现还是编程之美上讲的最清楚,这里我试图用自己的语言来总结一下)

首先是一个重要的规律:对于特定的数n, 所有从1到n上出现1的次数肯定等于个位上1的次数+十位上1的次数+百位上1的次数+千位上1的次数..... 比如

f(3)=1 只有个位上出现1 

f(13)=个位上出现1的有1 11, 十位上有10 11 12 13  = 2 + 4

f(23)=个位11的数量 11 21, 十位上有10 11 12 13 ...19 = 3 + 10

f(33)=个位1的数量 11 21 31, 十位上有10 11 12 13...19 = 4 + 10

f(93)=个位1的数量 有1 11 ... 91, 十位上有10 11 12 13...19 = 10 + 10

f(203)=个位1的数量 11 21..91,101,111,121..191,201 = 21, 十位 10,11,12..19,110...119=20, 百位100,101,199=100

f(12013)=百位上1的数量 100-199,1100-1199,2100-2199,...9100-9199....11100-11199, 总共12*100=1200  即高位数high*当前位数100

f(12113)=百位上1的数量 同上 高位数12*当前位数100=1200, 再加上12100-12113 = 13+1 即低位数low+1, 总共为high*100+low+1

通过上述的例子,可以发现一个规律,就是对于百位上1出现的次数,其受到三个因素影响:

1. 大于百位的,我们称之为高位high,  比如对于12013, 其high为12, 其在百位上出现1的次数受到高位high影响: 100-199, 1100-1199....9100-9199,10100-10199,11100-11199, 因为high的影响,为12*100=high*100

2. 对于百位自身cur,如果百位上的数为0,则没有1,如果等于1,则取决于低位low,比如113, 可以分解为 100-113, 即13+1=low+1. 如果大于1,比如813, 可分解为100-199, 即为100

所以现在需要解决的是然后获得高位high(12013中的12), 当前位cur(12013中的0), 以及低位low(12013中的13)

回到开头那个重要的规律,根据这个规律,我们要用一个变量来代表当前的位数,个位为1,十位为10.。依次类推,用fac来表示,fac由1开始,每处理完一位将fac乘以10,代表移到下一位

 

以12013为例,

高位high的计算方法是 12013/1000 = 12013/(百位fac*10) = 12

当前位cur的计算方法是 (12013/100)%10 = (12013/百位fac)%10 = 120%10 = 0

低位low的计算方法是 12013-(12013/100)*100 = 12013-(12013/百位fac)*百位fac = 12013 - 12000 = 13

 

则百位上1的总数有三种可能性:

1. 百位为0时 total = high*fac = 12*100 = 1200

2. 百位为1时 total = high*fac + low + 1 = 12*100 + 13 + 1

3. 百位为其他时 total = high* fac + fac = (high+1)*fac = (12+1)*100 

 

 1 package com.rui.microsoft; 2  3 public class Test30_Count1 { 4  5   public static void main(String[] args) { 6      7     long current = System.currentTimeMillis(); 8     System.out.println("TOTAL 1: " + countAll(120131111)); 9     System.out.println("TIME USED: " + (System.currentTimeMillis() - current));10     11     current = System.currentTimeMillis();12     System.out.println("TOTAL 1: " + cal(120131111));13     System.out.println("TIME USED: " + (System.currentTimeMillis() - current));14   }15   16   public static int cal(int n){17     int total = 0;18     int fac = 1;19     int high = 0, cur = 0, low = 0;20     21     while(n/fac!=0){22       //12013 -> 12013 - 12000=1323       low = n - (n/fac)*fac;24       //12013 -> (12013/100)%10=025       cur = (n/fac)%10;26       //12013 -> 12013/(100*10)=1227       high = n/(fac*10);28       29       switch(cur){30         case 0:31           //百位为032           //则百位上的1的数量完全取决于高位数33           total += high*fac;34           break;35         case 1:36           //百位为137           //则百位上的1的数量取决于高位数和低位数38           total += high*fac + low + 1;39           break;40         default:41           //百位大于142           total += (high+1)*fac;43           break;44       }45       46       fac *= 10;47     }48     49     50     return total;51   }52   53   54   55   public static int countAll(int n){56     if(n <= 0) return 0;57     int total = 0;58     for(int i = 1; i <=n; i++){59       total += count(i);60     }61     return total;62   }63   64   private static int count(int num){65     int total = 0;66     67     while(num>0){68       if(num%10 == 1){69         total++;70       }71       num = num/10;72     }73     74     return total;75   }76   77 }

 

用传统的方法和上述方法分别计算一个较长的数,比如120131111, 结果如下:

TOTAL 1: 124234672
TIME USED: 1372
TOTAL 1: 124234672
TIME USED: 0

 

可见其性能差距之大

通过此题 我彻底找到了取余的感觉。。。。