整数中k出现的次数

以剑指offer中“整数中1出现的次数”为例题，好好分析下更一般的整数中k出现的次数，道理是一模一样的，就是把1换成K而已。

输入n，统计1到n中k出现的次数；

假设n = 24,k = 2;

则1到24中，含有2的数字为    2,    12,    20,    21,    22,    23,    24,共计出现了8个2（没数错吧。。。）   

直接pass掉遍历法，又蠢又慢。

其次最容易想到的就是统计个十百千万....上每个位置上为2的数字，然后统计总和。

例如abcde，统计个十百千万每个位置上为2时的数字。

个位为2的数字总共有n1个

十位为2的数字总共有n2个

百位为2的数字总共有n3个

千位为2的数字总共有n4个

万位为2的数字总共有n5个

最后从1到abcde中2的出现次数sum = n1+n2+n3+n4+n5个

这里有个第一次容易理解错误的地方。

例如统计个位时，出现了22，统计十位时，也出现了错误，这岂不是重复统计了吗？

实则并没有，因为我统计个位时，我找到了22我也只关注这个数字的个位确实出现了2，因此加一，

同理我关注这个数字的十位确实也出现了2，因此也加一，1+1=2,正好22含有两个2，不矛盾。

重点是，题目统计的是k出现的次数，因此各个位置相互独立，自己管好自己就行了。

开始分析。

以31245为例,把我们想要定位的数字前面的部分记为a，后面的部分记为b（如我们想定位4这一位，那么a=312,b=5）

通过寻找规律，容易将数字分为3类，即小于k的，大于k的，等于k的，把等于k的放在最后，是因为这种相比其它两种情况稍稍有点复杂。

1.小于k的数字。

以31245的千位为例，1小于k（k=2）

我们想找到所有千位为2的数字，我们先把2放在千位咯

_     2    _    _    _

a能有多少种变化呢？显然0-2都可以，3不行，因为32XXX > 31245，故前半部分有3种，即a种变化，

确定了前面的部分，再看后面的，最大的22XXX为例，22999依然小于31245,因此XXX可以是0-999中的任何一个妖魔鬼怪，

故后半部分有10*10*10 = 10^3种取法，一共a*10^3种取法

这里可能会有疑问了，跟后面的245无关吗？

有个毛的关系啊你22999都取了，再往上都没有更大的数字了啊喂！

2.大于k的数字。

以31245的十位为例，4大于k(k = 2)

与上面相同的做法

_    _    _    2    _

312能取吗？3122X < 31245，必须可以取啊故前面有312+1=313，也就是a+1种

后面呢，还是把最大的拉出来遛遛，31229 < 312445，ok，没问题，可以取到0-9,且最大也就是31229了，

还是与这个最后一位5没有半毛钱关系，共有（a+1)*10种取法。

3.等于k的数字。

这里会有一丢丢的不一样，

_    _    2    _    _

首先分析从0-30中，30299<31245，OK一共有31*100，即a*100种取法

再看前面为31的时候，312XX，这时后面就只有0-45共计46种了，

因此最终共有31*100 +46种，也可以写成31*（46+54） + 46 = 32*46 + 31*54种

这样的思路是什么呢？

可以把0-99拆分成0-45和45-99两部分

当后面是0-45时，前面可以取0-31，因此共有32*46种，

而当后面是46-99时，前面只能取0-30，否则就会大于给定的这个数n了，因此共有31*54种。

把这三种情况整理合并一下。

a    _    b    （假设b有m位，例如b=39,则m=2,如不存在b，即我们判定的已经是最后一位了，则m=0，同理若a不存在，则a=0）

一.当x<k时，result = a*10^m

二.当x=k时，result = a*10^m+b+1

三.当x>k时，result = (a+1)*10^m

大功告成！统计每个位置上k出现的次数，然后全部累积起来，就可以得到最后的结果啦~

验证一下n=24,k=2

先统计个位上，x=4,a=2,b=0.m=0,x>k，看上面的公式result = (2+1)*10^0 = 3

再统计十位上的，x=2,a=0,b=4,m=1,x=k,result = 0*10 +4+1 = 5

最终结果为3+5=8,与我们前面统计出来的吻合

我们来数数个位上为2的有2,12,22        3个

十位上为2的有20,21,22,23,24            5个

完全吻合！

代码等下再补充在下面