【题目描述】 输入一个整数n，求从1到n这n个整数的十进制表示中1出现的次数。例如输入12，从1到12这些整数中包含1的数字有1、10、11和12，1一共出现了5次。 【思路分析】 1、简单粗暴效率低的解法 看到这道题目，我觉得只需要遍历从1~n所有的数字，统计每个数字中1出现的次数，再把他们相加即可，于是我写出了这样的代码。
int FindNumOf1(int n) { int count = 0; while (n) { if (n % 10 == 1) count++; n /= 10; } return count; } void TestNumOf1() { int n = 0; cin >> n; int count = 0; for (int i = 1; i <= n; i++) { count += FindNumOf1(i); } cout << count << endl; }上面的这种思路对每个数字都要做除法和求余数运算，它的时间复杂度为O(n*lgn)。当n输入非常大的时候，需要大量的计算，因此计算效率特别低，那仫有没有更加简单方便的算法呢？回答是肯定的。 2、高效直接的解法
假设输入的数字n，它的位数可以是任意的，且假设要计算的当前的位数是百位，此时1的个数可以分为以下几种情况： 1>、百位的数字是0，可能出现的1的次数由百位以上的位(更高位)决定。此时1的个数是更高位的数字*当前的位数。 2>、百位的数字是1，可能出现1的次数由高位和低位共同决定。 此时1的个数是更高位的数字*当前的位数+低位数字+1。 3>、百位的数字大于1，可能出现1的次数由高位决定。此时1的个数是(更高位的数字+1)*当前位数。
int FindNumOf12(int n) { int count = 0; //统计1的个数的变量 int bits = 1; //位数 int cur = 0, high = 0, low = 0; while (n / bits) { cur = (n / bits) % 10; //获得当前位的数字 high = n / (bits * 10); //高位数字 low = n - (n / bits)*bits; //低位数字 if (cur == 0) count += high*bits; if (cur == 1) count += (high*bits) + low + 1; if (cur > 1) count += (high + 1)*bits; //位数前移 bits *= 10; } return count; }在这里就分享结束了~~~
