至多替换数组a中一个元素 求两数组最小绝对差之和

给定两个长度相同的整数数组a和b，我们定义a和b的差值为对应位置元素的绝对差之和：
difference = |a[0] - b[0]| + |a[1] - b[1]| + … + |a[n-1] - b[n-1]
你可以将a中的任意一个元素替换为a中其他任意元素，也可以选择不对数组做任何修改。请你返回执行至多一次上述替换操作后，a和b可以达到的最小差值。要求解法的时间复杂度不超过O(n log n)。

当a = [1, 3, 5]，b = [5, 3, 1]时，输出应为solution(a, b) = 4。
具体推导如下：

• 若不修改数组a，差值为|1 - 5| + |3 - 3| + |5 - 1| = 8；
• 若将a[0]替换为a[1]，得到数组[3, 3, 5]，差值为|3 - 5| + |3 - 3| + |5 - 1| = 6；
• 若将a[0]替换为a[2]，得到数组[5, 3, 5]，差值为|5 - 5| + |3 - 3| + |5 - 1| = 4；
• 若将a[1]替换为a[0]，得到数组[1, 1, 5]，差值为|1 - 5| + |1 - 3| + |5 - 1| = 10；
• 若将a[1]替换为a[2]，得到数组[1, 5, 5]，差值为|1 - 5| + |5 - 3| + |5 - 1| = 10；
• 若将a[2]替换为a[0]，得到数组[1, 3, 1]，差值为|1 - 5| + |3 - 3| + |1 - 1| = 4；
• 若将a[2]替换为a[1]，得到数组[1, 3, 3]，差值为|1 - 5| + |3 - 3| + |3 - 1| = 6；
  因此最终答案为4。

1. 先计算不做任何修改时的原始差值总和total，我们的目标是找到一次替换操作能带来的最大差值减少量，最终最小差值就是total - 最大减少量，如果最大减少量为负则直接返回原始总和（即不做替换）。
2. 对每个位置i，原始贡献为|a[i] - b[i]|，如果将a[i]替换为a中元素x，新贡献为|x - b[i]|，该位置的减少量为|a[i] - b[i]| - |x - b[i]|。
3. 先将a数组排序，再对每个b[i]用二分查找找到a中最接近b[i]的元素，计算该元素对应的减少量，记录所有位置的最大减少量即可，整体时间复杂度符合O(n log n)要求。

import bisect

def solution(a, b):
    n = len(a)
    total = 0
    for ai, bi in zip(a, b):
        total += abs(ai - bi)
    sorted_a = sorted(a)
    max_gain = 0
    for ai, bi in zip(a, b):
        idx = bisect.bisect_left(sorted_a, bi)
        # 检查最接近bi的两个候选元素
        for j in [idx, idx-1]:
            if 0 <= j < n:
                current_gain = abs(ai - bi) - abs(sorted_a[j] - bi)
                if current_gain > max_gain:
                    max_gain = current_gain
    return total - max_gain

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