如何高效计算降序数组中所有数对的正差之和？

因为你的数组已经是降序排列的，我们可以通过数学推导找到线性时间的计算方式，不用遍历所有数对。

公式推导 #

假设数组为 a[0], a[1], ..., a[n-1]（a[0] ≥ a[1] ≥ ... ≥ a[n-1]），所有数对的正差之和可以拆分为两部分：

1. 每个元素 a[i] 作为被减数，会和它后面的 n-1-i 个元素组成数对，总贡献是 a[i] * (n-1-i)
2. 每个元素 a[j] 作为减数，会被它前面的 j 个元素减去，总贡献是 -a[j] * j

把两部分合并，总和就是：
总和 = Σ(a[i]*(n-1-i)) - Σ(a[i]*i)，其中 i 从 0 到 n-1

例子验证 #

用你给出的数组 [3,2,1]（n=3）：

• 第一部分求和：3*(2-0) + 2*(2-1) + 1*(2-2) = 3*2 + 2*1 + 1*0 = 6+2+0=8
• 第二部分求和：3*0 + 2*1 +1*2 = 0+2+2=4
• 总和：8-4=4，和预期结果一致。

代码实现（Python） #

def sum_of_positive_differences(arr):
    n = len(arr)
    sum1 = 0
    sum2 = 0
    for i in range(n):
        sum1 += arr[i] * (n - 1 - i)
        sum2 += arr[i] * i
    return sum1 - sum2

# 测试例子
arr = [3.0, 2.0, 1.0]
print(sum_of_positive_differences(arr))  # 输出 4.0

时间复杂度 #

• 如果数组已经是降序排列：O(n)，只需要一次遍历计算两个总和。
• 如果数组未排序：先排序（O(n log n)），再执行上述计算，总时间复杂度为O(n log n)，比 O(n²) 高效得多。

内容的提问来源于stack exchange，提问作者LogicalX