题目：

输入一个整数n求从1 到n这n个整数的十进制表示中1 出现的次数。

举例说明：

例如输入12 ，从1 到12这些整数中包含1 的数字有1、10、11 和12，1 一共出现了5次。

解题思路:

考虑将n的十进制的每一位单独拿出讨论，每一位的值记为 weight。

1) 个位

从1到n，每增加1，weight就会加1，当weight加到9时，再加1又会回到0重新开始。那么weight从0-9的这种周期会出现多少次呢？这取决于n的高位是多少，看图

image.png

以534为例，在从1增长到n的过程中，534的个位从0-9变化了53次，记为round。每一轮变化中，1在个位出现一次，所以一共出现了53次。
再来看weight的值。weight为4，大于0，说明第54轮变化是从0-4，1又出现了1次。我们记1出现的次数为count，所以：

count = round+1 = 53 + 1 = 54

如果此时weight为0（n=530），说明第54轮到0就停止了，那么：
count = round = 53。

2) 十位

对于10位来说，其`0-9周期的出现次数与个位的统计方式是相同的，见图：

image.png

不同点在于：从1到n，每增加10，十位的weight才会增加1，所以，一轮0-9周期内，1会出现10次。即rount*10。
再来看weight的值。当此时weight为3，大于1，说明第6轮出现了10次1，则：

count = round*10+10 = 5*10+10 = 60

如果此时weight的值等于0（n=504），说明第6轮到0就停止了，所以：

count = round*10+10 = 5*10 = 50

如果此时weight的值等于1（n=514），那么第6轮中1出现了多少次呢？很明显，这与个位数的值有关，个位数为k，第6轮中1就出现了k+1次(0-k)。我们记个位数为former，则：

count = round*10+former +1= 5*10+4 = 55

以此类推，更高位计算方式与十位是一致的。

4) 总结

将n的各个位分为两类：个位与其它位。
对个位来说：

若个位大于0，1出现的次数为round*1+1
若个位等于0，1出现的次数为round*1
对其它位来说，记每一位的权值为base，位值为weight，该位之前的数是former，举例如图：

image.png

则：
若weight为0，则1出现次数为round*base
若weight为1，则1出现次数为round*base+former+1
若weight大于1，则1出现次数为rount*base+base

比如：

534 = （个位1出现次数）+（十位1出现次数）+（百位1出现次数）=（53*1+1）+（5*10+10）+（0*100+100）= 214
530 = （53*1）+（5*10+10）+（0*100+100） = 213
504 = （50*1+1）+（5*10）+（0*100+100） = 201
514 = （51*1+1）+（5*10+4+1）+（0*100+100） = 207
10 = (1*1)+(0*10+0+1) = 2

实现代码:

#import <Foundation/Foundation.h>


/**
 求1-n这n个整数的十进制中1出现的次数

 @param n 最大的数字
 @return 1 出现的次数
 */
int numberOfOnwBetweenOneToN (int n){
    if (n < 1) {
        return 0;
    }
    
    int count = 0;
    // 当前 位数 进位
    int base = 1;
    // 高位
    int round = n;
    // 如果 高位 大于0 循环
    while (round > 0) {
        // 当前 位数 值
        int weight = round % 10;
        // 高位 个数
        round = round/10;
        // 当前 位数 1 出现次数
        count += round * base;
        
        // 当前 位数 为1
        if (weight == 1) {
            count += (n % base) + 1;
        }
        // 当前 位数 大于1
        else if(weight > 1) {
            count += base;
        }
        
        base = base * 10;
    }
    return count;
}


int main(int argc, const char * argv[]) {
    @autoreleasepool {

        printf("%d ", numberOfOnwBetweenOneToN(12));
    }
    return 0;
}

时间复杂度分析

由分析思路或者代码都可以看出，while循环的次数就是n的位数,logn（以10为底），而循环体内执行的操作都是有限次的，所以时间复杂度为O(logn)。