经典算法 统计数字问题(常数时间解决)

统计数字问题

一本书的页码从自然数1 开始顺序编码直到自然数n。书的页码按照通常的习惯编排，每个页码都不含多余的前导数字0。例如，第6 页用数字6 表示，而不是06 或006 等。数字计数问题要求对给定书的总页码n，计算出书的全部页码中分别用到多少次数字0，1， 2，…，9。
给定表示书的总页码的10 进制整数n (1≤n≤10^9 ) 。编程计算书的全部页码中分别用到多少次数字0，1，2，…，9。

输入示例

11

输出示例

1
4
1
1
1
1
1
1
1
1

输入示例

99999974

输出示例

68888887
79999998
79999998
79999998
79999998
79999997
79999997
79999992
79999987
79999837

c++代码

算法时间复杂度o(1)

#include<bits/stdc++.h>

using namespace std;

void countDigits(int num, vector<int>& digitCount) {
    int factor = 1;
    while (factor <= num) {
        int lower = num - (num / factor) * factor;
        int current = (num / factor) % 10;
        int higher = num / (factor * 10);
        for (int i = 0; i < 10; ++i) {
            digitCount[i] += higher * factor;
            if (i < current) digitCount[i] += factor;
            else if (i == current) digitCount[i] += lower + 1;
        }
        digitCount[0] -= factor;
        factor *= 10;
    }
}

int main() {
    int n;
    cout << "请输入书的总页码 n: ";
    cin >> n;
    vector<int> digitCount(10, 0);
    countDigits(n, digitCount);
    for (int i = 0; i < 10; ++i) {
        cout << digitCount[i] << endl;
    }

    return 0;
}//by wqs

题目解析

这个题目的暴力方法很容易想到，从0开始遍历一直到n，然后不断余10除10得到各位上的数字(这个操作常数时间可以解决)，

所以时间复杂度o(n)，可惜1≤n≤10^9,当n = 10^9会超时。

我的办法可以在常数时间内解决这个问题。

算法讲解

vector<int> digitCount(10, 0);//记录答案

我的办法就是一位数一位数的来，统计个位数出现多少次，然后统计十位数出现多少次，然后统计百位数出现多少次。

把他们加起来就是最终答案，那么怎么求呢。

int factor = 1;
while (factor <= num) {
    //...
    factor *= 10;
}

举两个例子

从0-135687、从0-175687789

例如求0-135687千位数上每个数字出现的次数(也就是n = 135687)

再来一个验证用例例如求0-175687789千万位数上每个数字出现的次数(也就是n = 175687789)

我会分三部分计算，对于任意一个数都可以分成三部分

cur、low、high、factor

n = 135687，求千位数

cur指当前千位数上的数也就是5

low指cur后面的数也就是687

high指cur前面的数也就是13

factor指当前的位数也就是1000

n = 175687789，求千万位数

cur指当前千万位数上的数也就是7

low指cur后面的数也就是5687789

high指cur前面的数也就是1

factor指当前的位数也就是10000000

int lower = num - (num / factor) * factor;
int current = (num / factor) % 10;
int higher = num / (factor * 10);

第一部分 从000000-129999、从000000000-099999999

为了方便计算我们引入前导0，当然根据题目要求我们最后要减去前导0。例如2表示为000002，0表示为000000，长度和n的长度一样。

先求从000000-129999千位数上每个数字出现的次数

000000

000001

…省略1000行左右,千位上0已经出现了1000次

001000

001001

…省略1000行左右,千位上1已经出现了1000次

002000

…省略8000行左右,这个时候0-9都已经出现了1 * 1000次

009999

…省略10000行左右这个时候0-9都已经出现了2 * 1000次

019999

…

129999

这个时候0-9都已经出现了13 * 1000次

事实上，这个值就是higher * factor.

从000000-129999千位数上每个数字出现的次数 = higher * factor

再比如辅助例子里面000000000-099999999千万位数上每个数字出现的次数 = higher * factor = 1 * 10000000

这说明0-9都有一部分是 higher * factor

for (int i = 0; i < 10; ++i) {
    digitCount[i] += higher * factor;
}

第二部分 从130000-134999，从100000000-169999999

现在求从130000-134999千位数上每个数字出现的次数

130000

130001

…0已经出现了1000次

130999

131000

131001

…1已经出现了1000次

131999

…

134999

从0-4已经出现了1000次

这个值就是factor.

从130000-134999千位数上0-current - 1数字出现的次数 += factor.

for (int i = 0; i < 10; ++i) {
    if (i < current) digitCount[i] += factor;
}

第三部分 从135000到135687，从170000000-175687789

现在求从135000-135687千位数上每个数字出现的次数

135000

135001

.

.

.

135687

5出现的次数就是行数

一共688行也就是low + 1

for (int i = 0; i < 10; ++i) {
    if (i == current) digitCount[i] += lower + 1;
}

去除前导0

000000

000001

…省略大概1000行

000999

001000

前导0的个数就是factor的大小

digitCount[0] -= factor;