算法 - 统计数字 - 易

给定数字 n (1<= n <= 1e9) ，计算1-n的每个数字，分别使用了多少次0-9,并且汇总

例如：

n = 11

结果：

数字：0 1 2 3 4 5 6 7 8 9

次数：1 4 1 1 1 1 1 1 1 1

建议

给你的代码不要复制粘贴，看完这个文档，理解了其中原理，按着代码打一遍，如果时间充足，使用c/c++将这个思路实现一下。看看执行时间。

关键思路

遍历每一个页码

将页码的每一位提取出来

对当前位数进行记录

分析

首先语法性的东西，比如读取文件，写文件之类的不说了，注意，读取文件的字符应该要转化为int。并且要求是1-1e9 之间

第二个，将页码的每一位都提取出来，这里我提供两个思路。

将当前页码转化为字符串，对字符串的每一个字符进行遍历。并转化为int整型。

for (int current = 1 ;current <= page ;current ++)
{
    // 将当前页码转化为字符串
    String istr = current + "";
    for (int j = 0 ; j < istr.length() ;j ++)
    {
        // 对每个位进行遍历，并转化为数字
        char c = istr.charAt(j);
        int index = Integer.parseInt(c+"");

        result[index] ++  ;
    }  
}

对页码整数分解出每一位。这里有两个方向的提取.

从低位 - 高位方向提取

// first num
int n1 = number % 10 ; 
// second num
int n2 = number / 10 % 10;
...

例子：
12345 % 10 = 5

12345 / 10 % 10 = 1234 % 10 = 4

注意：这样分解有一些问题，就是需要知道当前整数是是几位。否则将不会知道提取位到哪里停止

// 12345 提取第6位
12345 / 100000 % 10 = 0 

这个 0 也会被记录到result[0] 中，会出现错误。

这里有没有好方法？思考一下

从高位 - 低位方向提取

这个方式就有了一个很好的方法，来解决上述还要求数字位数的麻烦。我们从高位开始提取，提取到第一个大于0的数字时，开始记录。
这就需要一个标志位来做开关，告诉程序什么时候开始记录。

for(int current = 1 ;current<=page ;current ++)
{
    // 标记位 ： 是否开始记录位数字
    boolean flag = false ;
    for (int i = 9 ; i > 0 ;i --)
    {
        // Math.pow(x,y) 求x的y次方,返回的是double类型
        // java中类型转换比较复杂.这方面需要你留意
        // i 表示的是提取当前页码的第几位,比如i = 9 的时候
        // index = current / 1e8 % 10

        int zeronum = (new Double(Math.pow(10,i-1))).intValue(); 
        int index = current / zeronum % 10; 

        // 如果当前位 = 0 并且flag 是false 就不做处理
        if(index == 0 && flag == false)
        {
            continue ;
        }
        // 一旦当前为不为0 ,立即设置flag，以便低位0能够被正确的记录
        flag = true ;
        result[index] ++ ;
    }
}

最后，统计。构造一个10位数组，索引 0-9 的值对应着 0-9 出现的次数。
```
for (int k = 0 ;k < 10 ; k ++)
{
    System.out.println(result[k]);
}
```

思考

以上两种方法是我临时想到的两个方法。这里面的精髓就是对整数位数分解的思想，基本没什么营养。你也可以查阅一下资料，看是不是有更好的方法来分解整数。

第一种方法确实简单，思路清晰，一般实际使用的也是这种方法，效率高。程序设计中，简单的就是最好的。

第二种方法，看似比较复杂，并且效率比较低，但是也不是一无是处，这种求位运算中，从低位到高位，和从高位到低位，两种方式的简易程度是不一样的。

时间复杂度的问题，时间复杂度是个模糊概念，现阶段数据结构中考虑时间复杂度是看你循环的套数。两种方法中外部循环是n，内部循环设置为m，但是m<=9 , 所以时间复杂度是O(n*m) m<=9

但是通过程序来进行实际操作会发现，第一种方法的效率远远高于第二种。

当设置 page = 1234567 时可以看出两个程序所得到的结果以及运行时间

第一种方式比第二种方式效率高出了近10倍。

the result of the firstWay:
713306 1058985 758985 718985 713985 713385 713315 713307 713306 713306
the result of the secondWay:
713306 1058985 758985 718985 713985 713385 713315 713307 713306 713306
the time cusuming of the firstWay :89ms
the time cusuming of the secondWay :756ms

至于为什么，给你三个思路。