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

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) + …

你可以把所有的 ns 放在一边:

(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的总和s 跨越所有 n s 是 len(a) * sum(a) :

def concatenationsSum(a):
    sum_a = sum(a)
    return sum(10**digit_length(n) * sum_a for n in a) + len(a) * sum_a


def digit_length(n):
    """
    The number of base-10 digits in an integer.

    >>> digit_length(256)
    3

    >>> digit_length(0)
    1
    """
    return len(str(n))

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