如何高效计算两个数组元素的绝对差之和？

当然有更高效的解法！直接暴力枚举所有元素对的做法（时间复杂度O(p*q)）在数组规模较大时完全不适用——比如当p和q都达到1e5级别，暴力法会直接超时。我们可以利用排序+前缀和的思路，把时间复杂度优化到O(p log p + q log q)，这才是应对大数据量的正确姿势。

核心思路 #

我们要计算的是：
total = sum_{x ∈ P} sum_{y ∈ Q} |x - y|

利用绝对差的数学性质，结合排序和前缀和，可以快速计算单个元素x与数组Q所有元素的绝对差之和，再遍历P累加即可：

1. 先对数组Q进行排序，得到有序数组Q_sorted
2. 计算Q的前缀和数组prefix_Q，其中prefix_Q[i]表示Q_sorted前i个元素的总和（prefix_Q[0] = 0，prefix_Q[1] = Q_sorted[0]，以此类推）
3. 对于P中的每个元素x：
   • 用二分查找找到Q_sorted中第一个大于x的元素的位置pos，这样前pos个元素都≤x，剩余元素都>x
   • 前pos个元素与x的绝对差之和：x * pos - prefix_Q[pos]（因为每个元素y≤x，|x-y|=x-y，总和就是x*pos减去这些元素的和）
   • 剩余元素与x的绝对差之和：(prefix_Q[q] - prefix_Q[pos]) - x*(q - pos)（因为每个元素y>x，|x-y|=y-x，总和就是这些元素的和减去x*(q-pos)）
   • 把两部分结果相加，累加到总结果中

示例验证 #

拿你给出的例子来验证：

• P = [2,4]，Q = [4,-3,-4,4]
• 排序Q得到Q_sorted = [-4, -3, 4, 4]
• 计算前缀和prefix_Q = [0, -4, -7, -3, 1]

对于x=2：

• 二分查找找到第一个大于2的位置是2（前两个元素-4、-3≤2）
• 前2个元素的绝对差之和：2*2 - (-7) = 4 +7 =11（对应|2-(-4)|+|2-(-3)|=6+5=11）
• 剩余2个元素的绝对差之和：(1 - (-7)) -2*(4-2) =8 -4=4（对应|2-4|+|2-4|=2+2=4）
• 总和：11+4=15

对于x=4：

• 二分查找找到第一个大于4的位置是4（所有元素都≤4）
• 前4个元素的绝对差之和：4*4 -1=16-1=15（对应|4-(-4)|+|4-(-3)|+|4-4|+|4-4|=8+7+0+0=15）
• 剩余元素无，贡献0
• 总和：15

最终总结果：15+15=30，和示例计算结果一致。

代码实现（Python） #

import bisect

def calculate_total_abs_diff(P, Q):
    # 排序Q并计算前缀和
    sorted_Q = sorted(Q)
    q_length = len(sorted_Q)
    prefix_sum = [0] * (q_length + 1)
    for i in range(q_length):
        prefix_sum[i+1] = prefix_sum[i] + sorted_Q[i]
    
    total = 0
    for x in P:
        # 找到第一个大于x的元素位置
        pos = bisect.bisect_right(sorted_Q, x)
        # 计算小于等于x的元素的绝对差之和
        sum_less_or_eq = x * pos - prefix_sum[pos]
        # 计算大于x的元素的绝对差之和
        sum_greater = (prefix_sum[q_length] - prefix_sum[pos]) - x * (q_length - pos)
        total += sum_less_or_eq + sum_greater
    return total

# 测试示例
P_example = [2, 4]
Q_example = [4, -3, -4, 4]
print(calculate_total_abs_diff(P_example, Q_example))  # 输出30

时间复杂度分析 #

• 排序数组Q：O(q log q)
• 计算前缀和：O(q)
• 遍历数组P，每个元素做二分查找：O(p log q)
  整体时间复杂度为O(p log p + q log q)（如果P也排序的话其实不影响，本质是线性对数级），相比暴力法的O(pq)，在大数据量下性能提升极其明显。

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