原题目：
给定一个十进制数N，写下从1开始，到N的所有整数，然后数一下其中出现的所有"1"的个数。
例如：
N=2，写下1，2。这样只出现了1个"1"
N=12,写下 1,2,3,4,5,6,7,8,9,10,11,12。这样"1"的个数是5
请写出一个函数，返回1到N之间出现"1"的个数，比如 f(12)=5
package org.blogjava.arithmetic;
/** *//**
* @author Jack.Wang * @see ORATION: underline">http://jack2007.blogjava.net/
*/public class CountNumber 
{
private int count1Num(int num) { int sum = 0; while (num != 0) { sum += (num % 10 == 1) ? 1 : 0; num /= 10;
} return sum; } private int countNum(int n) { int sum = 0; for (int i = 1; i <= n; i++) { sum += count1Num(i); } return sum; } private int countNumNew(int n) { int count = 0; int factor = 1; int lower; int current; int higher; while (n / factor != 0) { lower = n - (n / factor) * factor; current = (n / factor) % 10; higher = n / (factor * 10); switch (current) { case 0: count += higher * factor; break; case 1: count += higher * factor + lower + 1; break; default: count += (higher + 1) * factor; } factor *= 10; } return count; } /** *//** * @param args */ public static void main(String[] args) { System.out.println("两个算法的结果相等"); /** *//** * 方法一： 这个问题看上出并不是一个难问题，因为不需要太多的思考，只要稍懂点程序的人都会想到，简单的设计如下。 * 这个方法很简单但是这个算法的致命问题是效率，它的时间复杂度是 O(N)*count(int num)函数的复杂度= * O(N)*logN。可见如果N很大时复杂度成线性增长。是否还有更好的方法，我说的是从算法复杂的角度考虑最优的方法？ */ long start = System.currentTimeMillis(); CountNumber cn1 = new CountNumber(); System.out.println("第一个算法的结果"+cn1.countNum(100000000)); long end = System.currentTimeMillis(); long time1 = end - start; /** *//** * 方法二： 这种方法分别分析N的每一位上1出现的可能性，读者可以自己按照归纳的思想分析一下，最终你会得出 * 一个结论，就是通过分析N而不是遍历1到N的每一个数就可以得出答案，如果N的长度为Len的话这种 算法的复杂度为O * 1. 如果位数上为0，1的数目由该位以上的数决定，并乘以该位的分位 比如百位上是0，高位上是14则百位上出现1的数目 * 2. 如果位数上为1，1的数目由高位和低位共同决定。 比如高位是14低位是112，则百位出现1的数目为 14×100+（112+ * 3. 如果位数上大于1，则百位出现1的数目为 （14+1）×100 */ start = System.currentTimeMillis(); CountNumber cn2 = new CountNumber(); System.out.println("第二个算法的结果"+cn2.countNumNew(100000000)); end = System.currentTimeMillis(); long time2 = end - start; System.out.println("第一个算法的时延比第二个算法的多" + (time1 - time2) / 1000 + "秒"); } /** *//** Console Out: 两个算法的结果相等 80000001 80000001 第一个算法的时延比第二个算法的多27秒 */}
本文来自：http://www.blogjava.net/Jack2007/archive/2008/10/16/234742.html
相关文章
