Java统计1到n的自然数中其中字符1出现的次数

用Java代码实现：1到n的自然数中其中 ‘1’  出现的次数，例如：1,11,12,100 中 ‘1’出现了5次。  

该问题的实现关键在于效率问题的考虑，如下是示例代码：

Coding：

/**
 * 统计在从1到n的正整数中1出现的次数
 * 
 * @author 吖大哥
 * @date Jun 11, 2014 10:26:21 PM
 */
public class CountOne {

	public static void main(String[] args) {

		int n = 10000000;

		long start = System.currentTimeMillis();
		int sum1 = CountOne.cnt(n);
		long end = System.currentTimeMillis();

		System.out.println(" sum1 历时 ：" + (end - start) + " 出现 1 的次数: " + sum1);

		long start2 = System.currentTimeMillis();
		int sum2 = CountOne.numOF(n);
		long end2 = System.currentTimeMillis();
		System.out.println(" sum2 历时 ：" + (end2 - start2) + " 出现 1 的次数: "
				+ sum2);

		long start3 = System.currentTimeMillis();
		int sum3 = CountOne.countNumOf1(n);
		long end3 = System.currentTimeMillis();

		System.out.println(" sum3 历时  ：" + (end3 - start3) + "  出现 1 的次数: "
				+ sum3);
	}

	/**
	 * 效率极差
	 * 
	 * @param n
	 * @return
	 */
	public static int cnt(int n) {
		int count = 0;
		String chr = "1";
		while (n >= 1) {
			String str = n + "";
			for (int i = 0; i < str.length(); i++) {
				if (str.indexOf("1") == -1) {// 如果字符串中没1 直接跳出循环
					break;
				}
				if (chr.equals(str.charAt(i) + "")) {
					count++;
				}
			}
			n--;
		}
		return count;
	}

	/**
	 * 效率稍好点
	 * 
	 * @param n
	 * @return
	 */
	public static int numOF(int n) {
		int number = 0;
		for (int i = 1; i <= n; ++i) {
			number += numberOf1(i);
		}
		return number;
	}

	public static int numberOf1(int n) {
		int number = 0;
		while (n != 0) {
			if (n % 10 == 1) {
				number++;
			}
			n = n / 10;
		}
		return number;
	}

	/**
	 * 效率惊人
	 * 
	 * 思路：分别计算 "1" 在每个位上面出现的次数，叠加起来
	 * 
	 * @param n
	 * @return
	 */
	public static int countNumOf1(int n) {
		if (n <= 0) {
			return 0;
		}
		int count = 0;
		int factor = 1;
		while (n / factor != 0) {
			int lowerNum = n - n / factor * factor;
			int currentNum = (n / factor) % 10;
			int highNum = n / (factor * 10);

			if (currentNum == 0) {
				// 如果为0,出现1的次数由高位决定
				count += highNum * factor;
			} else if (currentNum == 1) {
				// 如果为1,出现1的次数由高位和低位决定
				count += highNum * factor + lowerNum + 1;
			} else {
				// 如果大于1,出现1的次数由高位决定
				count += (highNum + 1) * factor;
			}
			factor *= 10;
		}
		return count;
	}

}