思路一:我们可以用最简单的办法先尝试一下,遍历1到n中间的每个整数对每个整數从低位到高位依次检查,如果有k出现则计数器自加
思路一最大的问题就是效率,当n非常大时就需要很长的运行时间。想要提高效率就要避开暴力法,从数字中找出规律
思路二:来自《编程之美》
假设有一个5位数N=ABCDE,我们现在来考虑百位上出现2的次数即:从0到ABCDE的数Φ,有多少个数的百位上是2分析完它,就可以用同样的方法去计算个位十位,千位万位等各个位上出现2的次数。
第一种情况:当百位上的数C小于2时:
1)当百位c为0时比如说12013,0到12013中哪些数的百位会出现2我们从小的数起, 200~299, , , … , , 也就是固定低3位为200~299然后高位依次从0到11,共12个再往下 已经大于12013,因此不再往下所以,当百位为0时百位出现2的次数只由更高位决定,等于更高位数字(12)x当前位数(100)=1200个
2)当百位C为1时,仳如说12113分析同上,并且和上面的情况一模一样最大也只能到,所以百位出现2的次数也是1200个
上面两步综合起来,可以得到以下结论:
—>当某一位的数字小于2时那么该位出现2的次数为:更高位数字x当前位数
第二种情况:当百位上的数C等于2时:
当百位C为2时,比如说12213那么,我们还是有200~299, , , … , 这1200个数他们的百位为2。但同时还有一部分,共14个(低位数字+1)所以,当百位数字为2时百位出现2的次数既受高位影响也受低位影响,结论如下:
—>当某一位的数字等于2时那么该位出现2的次数为:更高位数字x当前位数+低位数字+1
第三种情况:当百位上的数C大於2时:
当百位C大于2时,比如说12313那么固定低3位为200~299,高位依次可以从0到12这一次就把也包含了,同时也没低位什么事情因此出现2的次数是: (更高位数字+1)x当前位数。结论如下:
—>当某一位的数字大于2时那么该位出现2的次数为:(更高位数字+1)x当前位数
通过上述分析,我们可以得箌以下规律:
- 当某一位的数字小于i时那么该位出现i的次数为:更高位数字x当前位数
- 当某一位的数字等于i时,那么该位出现i的次数为:更高位数字x当前位数+低位数字+1
- 当某一位的数字大于i时那么该位出现i的次数为:(更高位数字+1)x当前位数