如题，对于一个整数，从1到n这n个数字中x出现的次数
直观的解法，可以从1-n，分别每位分解，计算x出现的次数，简单暴力，时间复杂度：O(nlog10n)
现在记录一O(lg10n)的思路：思路参见博客http://www.cnblogs.com/cyjb/p/digitOccurrenceInRegion.html
- 1-10， 个位中，任意的 X 都出现了 1 次。
- 1 -100， 十位中，任意的 X 都出现了 10 次。
- 1 - 1000，百位中，任意的 X 都出现了 100 次。
举例21345中1出现的次数：
个位出现：2134+1（2134个10，余下的5>1，所以会再出现一次）
十位出现：2130+10（213个100，每个出现10次，4>1，再出现10次）
百位出现：2100+100（21个1000，每个出现100次，3>1，再出现100次）
千位出现：2000+345+1（2个10000，每个出现1000次，1==1，再出现345+1次）
万位出现：0+10000（0个十万，2>1，即有10000次出现）
思路如上，根据思路，步骤如下：
1、数字n取其第i的左边位left：左边拥有left*pow(10,i-1)个x
数字n的第i位右边为right，右边第一位right_first：
a: right_first>x 加上右边的pow(10,i-1)个x；
b:right_first==x 加上右边right_first后的right%（pow(10,i-1)）+1个x；
2、重复往左取第i+1的左右，直至最高位取完后。
代码如下：
int NumofBetween1AndN(const int n, const int number)
{
int temp = n;
int res = 0;
int i = 0;
int mod = 1;
while (temp)
{
++i;
mod = mod * 10;
int left = n / mod*(mod / 10);
int right = n % mod ;
int right_first = right / (mod / 10);
res += left;
if (right_first > number)
res += (mod/10);
else if (right_first == number)
res += (right)%(mod/10) + 1;
temp = temp / 10;
}
return res;
}
此方法比较好理解，也好做，时间复杂度底。只是还是要充分理解才能写出代码，否则卡上半天也出不来。