十进制1出现的次数

 

给定一个十进制正整数N，求出从1开始到N的所有整数中，“1”出现的个数。

如：

N = 13 ，那么1,2,3，4,5,6,7……，10,11,12,13中“1”出现的个数为 6

 

解法一：

这个问题看上去并不困难，可以想到的就是 从1 开始遍历到N，将其中每一个数中含有的“1”相加起来，自然就得到了从1 到 N 所有“1”的个数和。

 

代码清单：

　　/*
	 * 判断一个整数中出现1 的次数
　　 * 用%运算，依次判断个位、十位、百位…上的数字是否为1
	 */
	public static int count1InAInteger(int n) {
		int count1 = 0;
		while (n != 0) {
			count1 += (n % 10 == 1) ? 1 : 0;
			n /= 10;
		}
		return count1;
	}

	/*
	 * for 遍历1 到 整数N，
　　 * 将所有整数中出现"1" 的次数累加
	 */
	public static int fun(int N) {
		int count = 0;
		for (int i = 0; i <= N; i++) {
			count += count1InAInteger(i);
		}
		return count;
	}

  

该方法很容易理解，实现也比较容易，最致命的问题是效率。如果N很大，则需要很长的时间才能得出计算结果。测试了一下，如果 N= 100 000 000，大约需要40秒

 

解法二：

想要提高效率，必须摒弃解法一中的遍历算法。能不能分析正整数每一位上“1”出现的次数，来解决问题呢？ 

假设N= abcdef ，这里 a,b,c,d,e,f 分别是N各个数位上的数字。如果现在要计算百位d 上出现“1”的次数，它将会受到三个因素的影响：百位上的数字，百位以下的数字（低位），百位以上的数字（更高位）。

<!--[if !supportLists]-->1、<!--[endif]-->如果百位上的数字为0，可知，百位上出现“1”的次数由更高位决定。比如12013，百位上出现“1”的情况是 100~199,1100~11991,2100~2199，……，11100~11199，一共有1200个，也就是说由更高位数字（12）决定，并且等于更高位（12）* 当前位数（100）= 1200

<!--[if !supportLists]-->2、<!--[endif]-->如果百位上的数字为1，百位上出现“1”的次数不仅受高位影响，还受低位的影响，比如12113，我们已经知道受高位影响出现“1”的次数为1200，受低位影响会出现“1”的数字 12100~12113 ，有13个

<!--[if !supportLists]-->3、<!--[endif]-->如果百位上的数字大于1，则百位上出现“1”的次数仅由更高位决定。比如12213，百位上出现“1”的情况是：100~199,1100~11991,2100~2199，……，11100~11199，12100~12199，一共1300个，[更高位（12）+1]*当前位数（100）

	public static int fun2(int N) {
		int count = 0;    // 记录次数
		int iFactor = 1;  // 当前位数
		int iLowerNum = 0; // 低位
		int iCurrNum = 0;	// 当前位上的数字
		int iHigherNum = 0;   // 更高位

		while (N / iFactor != 0) {
			iLowerNum = N - (N / iFactor) * iFactor;
			iCurrNum = (N / iFactor) % 10;
			iHigherNum = N / (iFactor * 10);

			switch (iCurrNum) {
			case 0:
				count += iHigherNum * iFactor;
				break;
			case 1:
				count += iHigherNum * iFactor + iLowerNum + 1;
				break;
			default:
				count += (iHigherNum + 1) * iFactor;
				break;
			}

			iFactor *= 10;
		}
		return count;
	}

 

该解法同样计算N = 100 000 000，只需要不到1毫秒的时间，相对于第一种效率至少提高了40 000 倍。