欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

从1到n整数中1出现的次数:O(logn)算法

程序员文章站 2024-03-15 17:03:00
...
  1. 题目描述
    输入一个整数n,求从1到n这n个整数的十进制表示中1出现的次数。例如输入12,从1到12这些整数中包含1的数字有1,10,11和12,1一共出现了5次。

  2. 题目来源
    第一次看到是在《剑指Offer》第2版上,面试题32。leetcode和牛客网上都有这道题。

  3. 本文的目的
    看了《剑指Offer》上的解法,我觉得不能算好:

这段解释描述有些不清晰,而且没有图,难以理解。
从书中给出的实现上来看,显得有些凌乱。
在这篇博客里,会给出一个我对这道题的解法,包括完整的解题思路,完整代码,时间复杂度分析,以及在leetcode和牛客网上的提交结果。

  1. 解题思路
    考虑将n的十进制的每一位单独拿出讨论,每一位的值记为weight。
  1. 个位
    从1到n,每增加1,weight就会加1,当weight加到9时,再加1又会回到0重新开始。那么weight从0-9的这种周期会出现多少次呢?这取决于n的高位是多少,看图:

以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周期的出现次数与个位的统计方式是相同的,见图:

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

如果此时weight的值等于0(n=504),说明第6轮到0就停止了,所以:
count = round10+10 = 510 = 50

如果此时weight的值等于1(n=514),那么第6轮中1出现了多少次呢?很明显,这与个位数的值有关,个位数为k,第6轮中1就出现了k+1次(0-k)。我们记个位数为former,则:
count = round10+former +1= 510+4 = 55
3) 更高位
更高位的计算方式其实与十位是一致的,不再阐述。

  1. 总结
    将n的各个位分为两类:个位与其它位。
    对个位来说:

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

则:
若weight为0,则1出现次数为roundbase
若weight为1,则1出现次数为round
base+former+1
若weight大于1,则1出现次数为rount*base+base
比如:

534 = (个位1出现次数)+(十位1出现次数)+(百位1出现次数)=(531+1)+(510+10)+(0100+100)= 214
530 = (53
1)+(510+10)+(0100+100) = 213
504 = (501+1)+(510)+(0100+100) = 201
514 = (51
1+1)+(510+4+1)+(0100+100) = 207
10 = (11)+(010+0+1) = 2
5. 完整代码
方法一:
暴力求解:

class Solution{
		public:
			int NumberOf1Between1AndN_Solution(int n){
				int count = 0;
				for (int i = 1; i <= n; ++i){
					count += numberOf1Ininteger(i);
				}
				return count;
			}
			int numberOf1Ininteger(int n){
				int times = 0;
				while (n){
					if (n % 10 == 1)
						times++;
					n /= 10;
				}
				return times;
			}
	
		};

方法二:找规律(如上述分析)

public int count(int n){
    if(n<1)
        return 0;
    int count = 0;
    int base = 1;
    int round = n;
    while(round>0){
        int weight = round%10;
        round/=10;
        count += round*base;
        if(weight==1)
            count+=(n%base)+1;
        else if(weight>1)
            count+=base;
        base*=10;
    }
    return count;
}
  1. 时间复杂度分析
    方法1时间复杂度为:间复杂度是O(N*logN)
    方法二时间复杂度为:时间复杂度为O(logn)。

还看到LeetCode上智商爆表的算法,我还没看该种解法,如下,感兴趣的话自己推算哈

int NumberOf1Between1AndN_Solution(int n)
    {
        int ones = 0;
        for (long long m = 1; m <= n; m *= 10) {
            int a = n/m, b = n%m;
            if(a%10 == 0)
                ones += a / 10 * m;
            else if(a%10 == 1) 
                ones += (a/10*m) + (b+1);
            else
                ones += (a/10+1)* m;
        }
        return ones;
    }
int countDigitOne(int n) {
    int ones = 0;
    for (long m = 1; m <= n; m *= 10)
        ones += (n/m + 8) / 10 * m + (n/m % 10 == 1 ? n%m + 1 : 0);
    return ones;
}