233. Number of Digit One

Leetcode Math

Given an integer $n$, count the total number of digit 1 appearing in all non-negative integers less than or equal to $n$.

Example:

Input: 13
Output: 6 
Explanation: Digit 1 occurred in the following numbers: 1, 10, 11, 12, 13.

分析

数字1的个数。最直接累加1到$n$中每个整数1出现的次数。可以每次通过对10求余数判断整数的个位数字是不是1。如果这个数字⼤于10，除以10之后再判断个位数字是不是1。如果输⼊数字$n$，$n$有$O(logn)$位，需要判断每⼀位是不是1，那么它的时间复杂度是$O(n\log n)$.

public int countDigitOne(int n) {
    if (n <= 0) return 0;
    if (n < 10) return 1;
    int count = 0;
    for (int i = 10; i <= n; i++)
        count += numberOfOne(i);
    return count;
}

private int numberOfOne(int n) {
    int count = 0;
    while (n > 0) {
        if (n % 10 == 1) count++;
        n /= 10;
    }
    return count;
}

但是过程中有非常多的重复计算，可以利用动态规划，如果把数字看作两部分：最高位和其他低位。那么1的个数是最高位中1的个数，然后加上保存下来的其他低位中的1的个数。

public int countDigitOne(int n) {
    if (n <= 0) return 0;
    if (n < 10) return 1;
    int[] countDigit = new int[n + 1];
    countDigit[1] = 1;
    int base = 10;
    // 计算每个数中出现1的次数
    for (int i = 10; i <= n; i++) {
        int highestDigit = i/base;
        if (highestDigit > 9) {
            base *= 10;
            highestDigit = i/base;
        }
        countDigit[i] =  (highestDigit == 1 ? 1: 0)
            + countDigit[i - highestDigit*base];
    }
    // 累加1...n中的所有1
    int count = 0;
    for (int i = 1; i <= n; i++)
        count += countDigit[i];
    return count;
}

以上两种算法的时间复杂度都是$O(n)$，当$n$非常大时，程序运算将非常慢，而且动态规划需要$O(n)$的空间。

那么有没有更好的方法呢？假设5位数字21221，那么可以把该数字分割成以下几部分：

• 0~9999, 也就是4位数中出现1的总次数，那么0～20000要再乘以2
• 20000～21221中最高位中1出现的次数：出现10000次，即10000到19999
• 剩余的1221中1出现的次数：递归求解

那么怎么求解$n$位数中出现1的总次数呢？其实就是$n-1$位数中出现1的总次数，加上以1开头的$n$位数个数。

public int countDigitOne(int n) {
    if (n <= 0) return 0;
    if (n < 10) return 1;

    //计算n的位数
    int number = n, numberOfDigits = 0;
    int highest = 0; // 最高位
    while (number > 0) {
        highest = number;
        number/= 10;
        numberOfDigits++;
    }

    // lowerCount[i]为i位数字中出现1的所有数量
    int[] lowerCount = new int[numberOfDigits];
    lowerCount[1] = 1;

    int base = 10;
    for (int i = 2; i < numberOfDigits; i++) {
        lowerCount[i] = base + 10 * lowerCount[i - 1];
        base *= 10;
    }

    int remaining = n - highest*base;
    int count  = 0;
    // n = 259, remaining = 59
    count = highest * lowerCount[numberOfDigits - 1] // i-1位数中出现的次数
        + (highest == 1 ? n - base + 1: base) + // 最高位1重复出现的次数
         + countDigitOne(remaining); // 除了最高位的次数
    return count;
}

⼀个数字$n$有$O(\log n)$位，因此这种思路的时间复杂度是$O(\log n)$.