原題目：
給定一個十進(jìn)制數(shù)N，寫下從1開始，到N的所有整數(shù)，然后數(shù)一下其中出現(xiàn)的所有"1"的個數(shù)。
例如：
N=2，寫下1，2。這樣只出現(xiàn)了1個"1"
N=12,寫下 1,2,3,4,5,6,7,8,9,10,11,12。這樣"1"的個數(shù)是5
請寫出一個函數(shù)，返回1到N之間出現(xiàn)"1"的個數(shù)，比如 f(12)=5
1
package org.blogjava.arithmetic;
2
3
/** *//**
4
* @author Jack.Wang
5 * @see http://jack2007.blogjava.net/
6
*/
7public class CountNumber 
{
8
9
private int count1Num(int num) {
10 int sum = 0;
11 while (num != 0) {
12 sum += (num % 10 == 1) ? 1 : 0;
13 num /= 10;
14
}
15 return sum;
16 }
17
18 private int countNum(int n) {
19 int sum = 0;
20 for (int i = 1; i <= n; i++) {
21 sum += count1Num(i);
22 }
23 return sum;
24 }
25
26 private int countNumNew(int n) {
27 int count = 0;
28 int factor = 1;
29 int lower;
30 int current;
31 int higher;
32 while (n / factor != 0) {
33 lower = n - (n / factor) * factor;
34 current = (n / factor) % 10;
35 higher = n / (factor * 10);
36 switch (current) {
37 case 0:
38 count += higher * factor;
39 break;
40 case 1:
41 count += higher * factor + lower + 1;
42 break;
43 default:
44 count += (higher + 1) * factor;
45 }
46 factor *= 10;
47 }
48 return count;
49 }
50
51 /** *//**
52 * @param args
53 */
54 public static void main(String[] args) {
55 System.out.println("兩個算法的結(jié)果相等");
56 /** *//**
57 * 方法一： 這個問題看上出并不是一個難問題，因?yàn)椴恍枰嗟乃伎迹灰远c(diǎn)程序的人都會想到，簡單的設(shè)計(jì)如下。
58 * 這個方法很簡單但是這個算法的致命問題是效率，它的時間復(fù)雜度是 O(N)*count(int num)函數(shù)的復(fù)雜度=
59 * O(N)*logN。可見如果N很大時復(fù)雜度成線性增長。是否還有更好的方法，我說的是從算法復(fù)雜的角度考慮最優(yōu)的方法？
請看方法二。
60 */
61 long start = System.currentTimeMillis();
62 CountNumber cn1 = new CountNumber();
63 System.out.println("第一個算法的結(jié)果"+cn1.countNum(100000000));
64 long end = System.currentTimeMillis();
65 long time1 = end - start;
66 /** *//**
67 * 方法二： 這種方法分別分析N的每一位上1出現(xiàn)的可能性，讀者可以自己按照歸納的思想分析一下，最終你會得出
68 * 一個結(jié)論，就是通過分析N而不是遍歷1到N的每一個數(shù)就可以得出答案，如果N的長度為Len的話這種 算法的復(fù)雜度為O
(Len)。 發(fā)現(xiàn)規(guī)律為
69 * 1. 如果位數(shù)上為0，1的數(shù)目由該位以上的數(shù)決定，并乘以該位的分位 比如百位上是0，高位上是14則百位上出現(xiàn)1的數(shù)目
為 14*100。
70 * 2. 如果位數(shù)上為1，1的數(shù)目由高位和低位共同決定。 比如高位是14低位是112，則百位出現(xiàn)1的數(shù)目為 14×100+（112+
1）
71 * 3. 如果位數(shù)上大于1，則百位出現(xiàn)1的數(shù)目為 （14+1）×100
72 */
73 start = System.currentTimeMillis();
74 CountNumber cn2 = new CountNumber();
75 System.out.println("第二個算法的結(jié)果"+cn2.countNumNew(100000000));
76 end = System.currentTimeMillis();
77 long time2 = end - start;
78 System.out.println("第一個算法的時延比第二個算法的多" + (time1 - time2) / 1000 + "秒");
79 }
80
81 /** *//**
82 Console Out:
83 兩個算法的結(jié)果相等
84 80000001
85 80000001
86 第一個算法的時延比第二個算法的多27秒
87 */
88}
89
本博客為學(xué)習(xí)交流用，凡未注明引用的均為本人作品，轉(zhuǎn)載請注明出處，如有版權(quán)問題請及時通知。由于博客時間倉促，錯誤之處敬請諒解，有任何意見可給我留言，愿共同學(xué)習(xí)進(jìn)步。