整数中1出现的次数(从1到n整数中1出现的次数) （两种方法：1、规律。2暴力求解）
题目描述
求出1 ~ 13的整数中1出现的次数,并算出100 ~ 1300的整数中1出现的次数？为此他特别数了一下1 ~ 13中包含1的数字有1、10、11、12、13因此共出现6次,但是对于后面问题他就没辙了。ACMer希望你们帮帮他,并把问题更加普遍化,可以很快的求出任意非负整数区间中1出现的次数。
规律( 1 的数目)
如果第 i 位(自右向左，从1开始标号)上的数字是0，则第 i 位可能出现 1 的次数由更高位决定(若没有高位，则视高位为0)，等于更高位数乘以当前位数的权重(10i-1)
如果第 i 位上的数字为 1，则第 i 位上出现 1 的次数不仅受更高位影响，还受低位影响(若没有低位，视低位为0)，等于更高位数乘以当前位数的权重 (10i-1) + (低位数 + 1)
如果第 i 位上的数字大于 1，则第 i 位上可能出现 1 的次数仅由更高位决定(若没有高位，视高位为0)，等于(更高位数 + 1)乘以当前位数的权重 (10i-1)
规律(x 的数目)
这里的 x 属于[1, 9]， 因为 x = 0 不符合下列规律，需要单独计算
首先要知道以下规律
- 从 1 至 10，在它们的个位数中，任意的 x 都出现了 1 次
- 从 1 至 100，在它们的十位数中，任意的 x 都出现了 10 次
- 从1至1000，在它们的百位数中，任意的x都出现了100次
- 依次类推，从 1 至 10i，在它们的左数第二位(右数第 i 位)，任意的 x 都出现了 (10i-1)次。这个规律很容易验证，这里不再多做说明
接下以 n = 2593, x = 5 为例来解释如何得到数学公式。从 1 至 2593中，数字 5 总计出现了 813 次，其中有 259次出现在个位，260次出现在十位，294次出现在百位，0次出现在千位
-
现在依次分析这些数据，首先是个位。从 1 至 2590 中，包含了 259 个 10，因此任意的 x 都出现了 259 次。最后剩余的三个数 2531,2592,2593，因为它们最大的个位数字 3 < x。因此不会包含任何 5. (也可以这么看， 3 < x， 则个位上可能出现的 x 的位数由更高位决定，等于更高位数字 (259) * 101-1 = 259)。
-
然后是十位。从 1 至 2500中，包含了25个100，因此任意的 x 都出现了 25 * 10 = 250 次。剩下的数字从 2501 至 2593，它们最大的十位数是 9 > x，因此会包含全部 10 个 5。最后总计 250 + 10 = 260。(也可以这么看，9 > x，则十位上可能出现的 x 的位数由更高位决定，等于更高位数字(25 + 1) * 102-1 = 260)
-
接下来是百位。从1至2000中，包含了2个1000，因此任意x都出现了2 * 100 = 200次。剩下的数字从2001至2593，它们最大的百位数字5 == x，这时候情况就略微复杂，它们的百位肯定是包含5的，但是不会包含全部100个。如果把百位是5的列出来，是从2500至2593，数字的个数与十位和个位数字有关，是93 + 1 = 94。最后总计 200 + 94 = 294。(也可以这么看， 5 == x，则百位上可能出现的x次数不仅受跟高位影响，还受低位影响，等于更高位数字 2 * 103-1 + (93 + 1))
-
最后是千位，现在已经没有更高位，因此直接看最大的千位数字 2 < x，因此不会包含任何 5 。(也可以这么看，2 < x，则千位上可能出现的x的次数仅由更高位决定，等于更高位数字 0 * 104-1 = 0)
到此为止，已经计算出全部数字 5 的出现次数。
总结
总结一下以上的算法，可以看到，当计算右数第 i 位包含的 x 的个数时：
-
取第 i位左边(高位)的数字，乘以 10i-1，得到基础值 a
-
取第 i 位数字，计算修正值
-
如果大于 x , 则结果为 a + 10i-1
-
如果小于 x，则结果为 a
-
如果等于 x，则取第 i 位右边(低位)数字，设为 b，最后结果为 a + b + 1
代码
#include <iostream> using namespace std; int oneNum(int n) { int cur=n%10;//当前位 int high=n/10;//相对于当前位的高位部分 int low=0;//低位部分 int count=0;//计数 int base=1;//基 while(n/base) { if(cur==0)//题目中要求找1 故小于1的只有0 { count+=high*base;//高位部分乘以基（见上文的算法总结和规律） } else if(cur==1) { count+=high*base+low+1; } else{ count+=(high+1)*base; } base*=10; cur=high%10; high=n/(base*10); low=n%base; } return count; } int main() { int n; while(cin>>n) { cout<<oneNum(n)<<endl; } return 0; }
由分析思路或者代码都可以看出，while循环的次数就是n的位数,logn（以10为底），而循环体内执行的操作都是有限次的，所以时间复杂度为O(logn)。
暴力求解：
方法：对1到n中的每一个数，分别判断其中1的个数。
复杂度：O(n*logn)
int oneNum_b(int n) { assert(n>=0); int count=0; int curNum=1; for(int i=1;i<=n;i++) { curNum=i; while(curNum) { if(curNum%10==1) count++; curNum/=10; } } return count; }