查找列表中所有串联整数对之和的高效算法

Question

我在我的一次面试实践中遇到了这个问题，并且遇到了一个问题，它的时间复杂度比 O(N^2) 更好。在某种程度上，您必须访问列表中的每个元素。我考虑过使用哈希表，但它仍然必须执行哈希表并填充它然后进行计算。基本上我的解决方案是一个嵌套的 for 循环，我也包含了我的代码，它在 4 秒内通过了除时间异常之外的所有内容。

我的代码：

def concatenationsSum(a):
    sum = 0
    current_index_looking_at = 0
    for i in a:
        for x in a:
            temp = str(i)+str(x)
            sum += int(temp)
    return sum

问题描述：

Given an array of positive integers a, your task is to calculate the sum
of every possible a[i] ? a[j], where a[i] ? a[j] is the concatenation
of the string representations of a[i] and a[j] respectively.
    
    Example
    
    For a = [10, 2], the output should be concatenationsSum(a) = 1344.
    
    a[0] ? a[0] = 10 ? 10 = 1010,
    a[0] ? a[1] = 10 ? 2 = 102,
    a[1] ? a[0] = 2 ? 10 = 210,
    a[1] ? a[1] = 2 ? 2 = 22.
    So the sum is equal to 1010 + 102 + 210 + 22 = 1344.
    
    For a = [8], the output should be concatenationsSum(a) = 88.
    
    There is only one number in a, and a[0] ? a[0] = 8 ? 8 = 88, so the answer is 88.
    
    Input/Output
    
    [execution time limit] 4 seconds (py3)
    
    [input] array.integer a
    
    A non-empty array of positive integers.
    
    Guaranteed constraints:
    1 ? a.length ? 10^5,
    1 ? a[i] ? 10^6.
    
    [output] integer64
    
    The sum of all a[i] ? a[j]s. It's guaranteed that the answer is less than 2^53.

Answer 1

两个整数的连接：

m ? n

等于：

10**digit_length(n) * m + n

所以每个列表项与给定整数的串联总和：

(a[0] ? n) + (a[1] ? n) + …

等于：

(10**digit_length(n) * a[0] + n) + (10**digit_length(n) * a[1] + n) + …

你可以把所有的n放在一边：

(10**digit_length(n) * a[0]) + (10**digit_length(n) * a[1]) + … + n + n + …

请注意，数组的每个元素都乘以一个仅取决于n的值：

10**digit_length(n) * (a[0] + a[1] + …) + n + n + …

再次简化：

10**digit_length(n) * sum(a) + len(a) * n

sum(a)不会改变，len(a) * n所有ns的s总和是len(a) * sum(a)：

m ? n

当所涉及的整数的上限是常数时，这会在线性时间内运行。只要浮点数学对于所涉及的整数大小足够精确，您也可以使用math.log10使digit_length速度更快（如果没有，还有比通过字符串更好的实现方法 - 但可能没有更短或更易于理解的方法） .

Answer 2

而不是分别在每个数字前面加上每个数字，只需在它前面加上总和一次。那么，它只作为尾部出现一次而不是 N 次，所以只需将其添加 N-1 次（或等效地，将总和添加 N-1 次）。

def concatenationsSum(a):
    sum_ = sum(a)
    return sum(int(str(sum_) + str(x)) for x in a) + (len(a) - 1) * sum_

运行时间是 O(N)。repl.it 上的演示只有 1000 个值，输出：

original result 460505045000 in 3.3822 seconds
  faster result 460505045000 in 0.0017 seconds
Same result? True