美文网首页
【剑指Offer学习】【面试题32:求从1到n的整数中1出现的次

【剑指Offer学习】【面试题32:求从1到n的整数中1出现的次

作者: 林大鹏 | 来源:发表于2018-02-10 15:02 被阅读29次

题目:

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

举例说明:

例如输入12 ,从112这些整数中包含1 的数字有11011121 一共出现了5次。

解题思路:

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

1) 个位

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

image.png

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

count = round+1 = 53 + 1 = 54

如果此时weight0(n=530),说明第54轮到0就停止了,那么:
count = round = 53

2) 十位

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

image.png

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

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的各个位分为两类:个位与其它位。
对个位来说:

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

image.png

则:
weight为0,则1出现次数为round*base
weight1,则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)

相关文章

网友评论

      本文标题:【剑指Offer学习】【面试题32:求从1到n的整数中1出现的次

      本文链接:https://www.haomeiwen.com/subject/sbuctftx.html