十进制1出现的次数_JAVA_编程开发_程序员俱乐部

class="p0" style="margin-bottom: 0pt; margin-top: 0pt;">?

给定一个十进制正整数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?倍。