题目

写一个函数

int solution(int N);

即给定一个整数N，返回数字1在所有不超过 N 的正整数的十进制表示中出现的次数。

例如，给定N = 13，该函数应返回6，因为：

• 所有不超过13的正整数是1、2、3、4、5、6、7、8、9、10、11、12 和13；
• 数字1共出现六次：一次在数字1中，一次在数字10中，两次在数字11中，一次在数字12中，一次在数字13中。

N 是[0.. 100,000,000]范围内的整数。

解法1

暴力求解：遍历每一个数，对每一个数求1的个数，然后加起来得和。

int solution(int N)//统计1-n中1的个数
{
	int ans=0;
	for(int i=1; i<=n; i++) {
		for(int j=i; j>0; j/=10) {
			if(j%10==1)
				ans ++;
		}
	}
	return ans;
}

算法时间复杂度：$O(nlgn)$

解法2

考虑两位数。将一个正整数中1的个数分成两部分，一部分是个位上出现1的数目f1(n)，一部分是十位上出现1的数目f2(n) 。

n=10， f1(10)=1（1-10个位出现的1的个数为1），f2(10)=1（1-10个位出现的1的十数为1）。

举一些代表性的数：

n	f1(n)	f2(n)	f(n)
10	1	1	2
11	2	2	4
12	2	3	5
13	2	4	6
20	2	10	12
21	3	10	13
22	3	10	13
23	3	10	13
30	3	10	13
31	4	10	14
32	4	10	14
33	4	10	14

先来看十位，当十位上的数为1时，

n	f2(n)
10	1
11	2
12	3
13	4

f2(n)=当前数个位数字+1；

当十位上的数大于1时，

n	f2(n)
20	10
21	10
22	10
23	10
30	10
31	10
32	10
33	10

f2(n) = 10，也就是说此时十位上1的数目仅仅和十位有关系，也就是十位的位因子10。

再来看个位，当个位上的数为1的时候

n	f1(n)
11	2
21	3
31	4

f1(n) = 当前数十位数字+1；

当个位上的数大于1时，

n	f1(n)
22	3
23	3
32	4
33	4

f1(n) = 当前数十位数字+1；

还有当个位上的数等于0时，

n	f1(n)
10	1
20	2
30	3

f1(n) = 当前数十位数字。

这还不够，我们还没有分析两位数以上的数字，根据上面的分析，我们将当前位分为三种情况：=0，=1，>1。

当百位上的数字是0的时候，假设n=12013。此时1-12013的所有整数中，百位上出现1的数是100~199，1100~1199，2100~2199……11100~11199。也就是12个100，1200个。也就是说此时百位上1的数目是由高位（12）决定的，而且等于高位（12）* 当前位因子（100）。

当百位上的数字是1的时候，假设n=12113。此时1-12113的所有整数中，百位上出现1的数是100~199，1100~1199，2100~2199……11100~11199，12100~12113。也就是13个100，1300个。也就是说此时百位上1的数目是由高位（12）决定的，而且等于（高位（12）+1）* 当前位因子（100）。

还有一个小问题就是如何求一个数的高位和低位，还有当前位。这和当前位的位因子有关系。

对于12345，假设当前位是百位（100），则

• 低位数字：12345 - (12345 / 100) *100 = 45
• 高位数字：12345 / (100 * 10) = 12
• 当前位数字：12345 / 100 = 123，123 % 10 = 3。

以上分析可以写出完整代码。

Java实现

int solution(int N){
    int ans = 0;
    int lowNum = 0; // 当前位的低位的数字
    int currNum = 0; // 当前位数字
    int highNum = 0; // 当前位的高位的数字

    for(int factor = 1; factor <= N; factor *= 10) { // 位因子
        lowNum = N - (N / factor) * factor;
        currNum = (N / factor) % 10;
        highNum = N / (factor * 10);
        if(currNum == 0) {
            ans += highNum * factor;
        } else if(currNum == 1) {
            ans += highNum * factor + lowNum +1;
        } else {
            ans += (highNum + 1) * factor;
        }
    }
    return ans;
}

时间复杂度只与N的位数有关，为$O(lgn)$。

参考资料

1. 求1-N中十进制正整数1的个数