首页 > 代码库 > 剑指offer (32) 从1到n整数中1的出现次数
剑指offer (32) 从1到n整数中1的出现次数
题目：输入一个整数，求从1到n这个n个整数的十进制表示中1的出现次数
方法一：最直观的解法 T(n) = O(nlgn)
int NumberOf1Between1AndN_Solution1(unsigned int n){ int number = 0; for(unsigned int i = 1; i <= n; ++ i) number += NumberOf1(i); return number;}int NumberOf1(unsigned int n){ int number = 0; while(n) { if(n % 10 == 1) number ++; n = n / 10; } return number;}
方法二：
假设N = abcde(N的十进制表示，e为个位)
如果要计算百位c出现1的次数，将会受到3个因素的影响：
(1) 百位上的数字
(2) 百位以下的数字(低位数字)
(3) 百位以上的数字(高位数字)
如果百位数字为0，百位出现1的次数取决于 其高位数字
比如 12013, 出现1的情况可能是：100-199 1100-1199 2100-2199 ..... 10100-10199 11100-11199
可以看到出现1时，低位(即cde)都是 100-199这100种情况，而高位(即ab两位)从 0，1，2，3...11 刚好为12对，即高位数字12
所以：这时百位出现1的次数：高位数字12 × 当前位数100 = 1200
如果百位数字为1，百位出现1的次数取决于 其高位数字和低位数字
比如12113，先按照上面一种情况所述：100-199 1100-1199 2100-2199 ..... 10100-10199 11100-11199
这个时候百位为1，则 还有其他情况可以出现1：12100 12101 12102 12103 .....12113 (注意到高两位都为12，低位从100到113，即低位13+1=14种情况)
所以：这时百位出现1的次数：高位数字12 × 当前位数100 + 低位数字13 + 1 = 1214
如果百位数字大于1，百位出现1的次数取决于 其高位数字
比如12213，按照第一种情况所述：100-199 1100-1199 2100-2199 ..... 10100-10199 11100-11199 12100-12199
注意：百位数字大于1，所以不要忘记了 12100-12199 这种情况
所以：这时百位出现1的次数：（高位数字12 + 1 ）× 当前位数100 = 1300
int OneNum(const int num){ assert(num >= 0); int factor = 1; int count = 0; int curNumber = 0; int highNumber = 0; int lowNumber = 0; while (num / factor != 0) { lowNumber = num - (num / factor) * factor; // 低位数字 curNumber = (num / factor) % 10; // 当前位数字 highNumber = (num / factor) / 10; // 高位数字 switch (curNumber) { case 0 : count += highNumber * factor; break; case 1 : count += highNumber * factor + lowNumber + 1; break; default : count += (highNumber + 1) * factor; break; } factor *= 10; } return count;}