提问人：Mooch 提问时间：9/11/2023 更新时间：9/11/2023 访问量：84
如何优化将整数转换为字符串并返回并将它们求和 [已关闭]
How to optimize converting integers to strings and back and summing them [closed]
问：
今天我正在对 Code Signal 进行练习预筛选测试，其中一个问题就是这个。
给定一个整数数组 a，返回所有 a[i] º a[j] 的总和，其中 a[i] º a[j] 定义为 a[i] 和 a[j] 的串联，例如，如果 a[0] = 1 且 a[i] = 2，则 a[i] º a[j] = 12。
可以获得正确的输出，但对于其中一个隐藏的测试用例来说太慢了。缓存，也不够快。我怎样才能使它更有效率？sum(int(str(ai) + str(aj) for ai in a for aj in a)str(ai)str(aj)
答：
-2赞
SAI PRANEETH REDDY K
9/11/2023
#1
def concatenatedSum（a）： 结果 = 0
for num in a:
current = num
while current > 0:
result += current % 10
current /= 10
return result
#example
a = [1， 2， 3]
打印（串联总和（a））
0赞
UpAndAdam
9/11/2023
#2
第一步是，如果列表中总是有一个数字，则不要使用字符串来构建连接：
sum(10*i + j for i in a for j in a)
如果可以给你任何数字，那么你可以按照@mozway指出的那样，生成一个系数的旁表
from math import log10, ceil
l = [10**int(ceil(log10(x+1))) for x in a]
out = sum(n*i+j for i in a for n, j in zip(l, a))
但是这些解决方案并没有将 O（N^2） 更改为更好的方法，它们只是降低了系统调用在构造字符串并将其作为整数返回时的可怕成本，这是一个非常缓慢的过程，应该删除。
但是，您可以真正大幅加快速度，并在一次通过 O（N） 中完成。
更新以修复长度平方为错误乘数的问题
a = list(...) # your input
sum = 0
len = len(a) # get the length
# you are going to count each element as the one and the ten digit in list^2 number of occurences.. so just multiply
for i in list:
sum += (int(i) + (int(i)*10))*len
return sum
2赞
mozway
9/11/2023
#3
如果你只有个位数，你可以简单地乘以 10：
sum(10*i + j for i in a for j in a)
这比使用字符串快 4 倍左右。
如果可以拥有任意位数的数字：
from math import log10, ceil
l = [10**int(ceil(log10(x+1))) for x in a]
out = sum(n*i+j for i in a for n, j in zip(l, a))
在 20 个项目（400 个组合）上，这大约快了 60%，在 1000 个项目（1M 个组合）上快了 3 倍。
评论