python - 如何即时判断 '0'到 '9'在特定范围内被使用了多少次

Question

我想计算“0”到“9”在特定范围内使用了多少次

例如112有两个“1”和一个“2”

感谢您的建议，我现在更改了代码。

但它没有达到我想要的效率。

num = int(input('n : '))
start_time = time.time()
num_arr = [0] * 10
progress_arr = ['%d' % (num * (i / 100)) for i in range(1, 101)]

for i in range(1, num + 1):
    if str(i) in progress_arr:
        print(str(progress_arr.index(str(i)) + 1) + '%')
    for digit in str(i):
        num_arr[int(digit)] += 1

print('Time : %.2f' % (time.time() - start_time))
print(num_arr)

当我输入 1000 作为 n 时，我的程序将立即打印这个 arr

[192、301、300、300、300、300、300、300、300、300]

这意味着1到1000，“0”已使用 192 次，“1”已使用 301 次……

但是当我输入 2,000,000,000 作为 n 时，我的程序将在之后打印结果11 分钟(使用 pypy3、Ryzen 2600)。

所以我想更改我的代码，以尽可能有效地立即获得非常大的数字的结果。

在我之前的问题中，我提到了 O(N) 的时间复杂度，这让你感到困惑，因为我对算法和时间复杂度的理解很差。所以我删除了它。

我想知道的只是高效的算法。

我试图通过分析增量结果的差异来找到具体的规律，但这并不容易。

Answer 1

为了有效地解决这个问题，你不能一一地遍历数字并计算它们的位数。您需要应用数学。

---

假设该范围的上限是 123456。让我们尝试计算出每个可能的数字在此范围(百位中)出现了多少次。

对于每 1000 个连续整数，每个可能的数字在百位中出现 100 次，除非该数字是前导零。有 123456//1000=123 个完整的 1000 整数 block ，还剩下 123456%1000=456 个从 123001 到 123456 的整数。完整的 block 为我们提供了百位中每个数字的 123*100=12300 次出现，由于前导零，数字 0 出现了 99 次。

在 123001 到 123456 范围内，0 在百位中出现了 99 次，1 到 3 中的每个数字出现了 100 次，4 出现了 57 次。

---

弄清楚如何形式化这个逻辑，足以在程序中实现它，并将其应用到每个数字位置，您将能够轻松处理远大于 20 亿的输入。