面试题32：从1到n整数中1出现的次数

2019-03-19 本文已影响0人 liuqinh2s

面试题32：从1到n整数中1出现的次数

题目

输入一个正整数n，求从1到n这n个整数的十进制表示中1出现的次数。例如输入12，从1到12这些整数中包含1的数字有1，10，11和12。1一共出现了5次。

暴力算法

遍历从1到n的数，对每一个数进行解析，每个数的解析时间是 $\log_{10} n$ 。

算法时间复杂度是 $n\log(n)$

public int NumberOf1Between1AndN_Solution(int n) {
    int sum = 0;
    for(int i=1;i<=n;i++){
        sum+=countOne(i);
    }
    return sum;
}

private int countOne(int n){
    int count = 0;
    while(n!=0){
        int a = n%10;
        if(a==1){
            count++;
        }
        n/=10;
    }
    return count;
}

剑指offer上的解法

以n=21345为例，如果我们能把问题分解为：分别求出1~1345和1346~21345的解，然后实际只去求1346~21345，而对于求1~1345使用递归，那么问题就解决了。

如何求1346~21345的解呢？

我们将分类讨论，最高位1出现多少次？其余位1出现多少次？

最高位1出现在10000~19999中，总共10000个，但这不是一般情况，如果是10000~11345呢？（如果n=11345），所以这里要分类讨论一下，如果最高位小于2，那么总共出现1的数应该就是后面所有的数再加1，也就是1345+1（加1是因为从0算起）。剩余4位中比如千位是1，然后其它3位随便是什么，这样就有 $1\times10^3$ 个，4位就是： $4\times10^3$ ，然后最高位还可以分别是1和2，所以总共是： $2\times4\times10^3$ 个。抽象成一般原理： $最高位的值\times剩余位数\times10^{剩余位数-1}$

因为只跟n的位数有关，所以算法时间复杂度是： $\log n$

public int NumberOf1Between1AndN_Solution(int n) {
    String s = Integer.toString(n);
    char[] c = s.toCharArray();
    return recurse(c, 0);
}

private int power10(int n){
    int result = 1;
    for(int i=0;i<n;i++){
        result*=10;
    }
    return result;
}

private int recurse(char[] c, int i){
    if(i==c.length-1){
        return 1;
    }
    int sum = 0;
    // 最高位1的个数
    if(c[i]>'1'){
        sum += power10(c.length-1-i);
    }else{
        sum += charToInt(c, i+1)+1;
    }
    // 其余位1的个数
    sum += (c[i]-'0')*(c.length-1-i)*power10(c.length-2-i);
    return sum+recurse(c, i+1);
}

private int charToInt(char[] c, int index){
    int temp = 0;
    for(int j=index;j<c.length;j++){
        temp *= 10;
        temp += (c[j]-'0');
    }
    return temp;
}

编程之美上的解法

如果我们发现了一个规律：

1到10，个位数是1的个数是：1

1到100，十位数是1的个数是：10

1到1000，百位数是1的个数是：100

$\vdots$

以此类推

依旧以21345为例。

先统计其中个位商上现1的个数：21340是10的2134倍，也就意味着以10为周期1会不断的在个位上出现2134次，再加上21341到21345中出现的21341这个也是个位出现1，所以总共是2135个个位1。

然后统计十位上出现1的个数：21300是100的213倍，以100为周期，十位每次出现10个1，也就是213*10，再加上从21301到21345，中2131x，这些10个数，总共是213*10+10

其实规律这就已经出来了，写成代码如下：

public int NumberOf1Between1AndN_Solution(int n) {
    int sum = 0;
    int count = 10;
    while(n*10/count!=0){
        int a = n/count;
        int b = n%count;
        if(b>(2*count/10)){
            b = (count/10);
        }else if(b>=(count/10)){
            b = n%(count/10)+1;
        }else{
            b = 0;
        }
        sum += a*count/10+b;
        count*=10;
    }
    return sum;
}

算法复杂度也很容易得到： $\log n$

面试题32：从1到n整数中1出现的次数