算法 - 统计数字 - 易
给定数字 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
至于为什么，给你三个思路。
- 在java中，Math.pow()函数是一个很耗费时间的函数
- 第二种方式中，每一个页码不管长度是多少，都要循环9次。而第一种方式中，可以轻而易举的得到页码的长度，故而每一个页码循环的次数是页码长度。
- 新建的Double 对象转化int整型耗时较长。
针对不同的编程语言，上述的行为都不太一样。对于c++ / c语言，上述代码会执行的快一些，这也解释了一个知识点：编译语言比解释语言要快。
c/c++代码不写了，你自己实践一下。
网友评论