我想计算在特定范围内使用“ 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)的时间复杂度,由于对算法和时间复杂度的了解不足,这使您感到困惑。所以我删除了它。
我想知道的只是高效的算法。
我试图通过分析增量结果的差异来找到特定的规则,但这并不容易。
最佳答案
为了有效地解决这个问题,您不能一一列举数字。您需要应用数学。
假设范围的上限是123456。让我们尝试找出该范围内每个可能的数字出现几百次。
对于每1000个连续的整数,每个可能的数字在百位出现100次,除非该数字是前导零。有123456 // 1000 = 123个完整的1000整数块,剩余123456%1000 = 456个从123001到123456的整数。完整的块使我们在百位中的每个数字出现123 * 100 = 12300次,由于前导零,数字0减去99。
在123001到123456的范围内,0在百位出现99次,从1到3的每个数字出现100次,而4个出现57次。
弄清楚如何将该逻辑形式化到足以在程序中实现该逻辑并将其应用于每个数字位,您就可以轻松地处理大于20亿的输入。
关于python - 如何立即确定在特定范围内使用了“0”到“9”的次数,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/62124898/