python - 找到两个数组之间的最小可能差

我正在努力找出一种有效的算法来执行以下任务:
给定两个数组A和B的长度相等，两个数组之间的差定义为:

diff = |a[0]-b[0]| + |a[1]-b[1]| +...+|a[a.length-1]-b[b.length-1]|

我需要找到A和B之间的最小可能差值，并且允许我最多用A中的任何其他元素替换A中的一个元素。请注意，不需要执行替换。
例如:

A = [1,3,5]
B = [5,3,1]

如果将A [2]替换为A [0]，则两个数组之间的差为:

|1-5| + |3-3| + |1-1| = 4

这是两个阵列之间最小的可能差异。用A中的另一个元素替换A中的元素不会导致A和B之间的差异较小。
我将如何解决这个问题？我知道如何解决O(n ^ 2)(强力)中的问题，但是努力寻找一种更有效的方法。
谢谢!

最佳答案

我将执行Shridhar的建议，即在O(n log n)的时间内分别为每个元素确定最佳修改，并采用最佳修改。

import bisect


def abs_diff(x, y):
    return abs(x - y)


def find_nearest(sorted_a, y):
    i = bisect.bisect(sorted_a, y)
    return min(
        sorted_a[max(i - 1, 0) : min(i + 1, len(sorted_a))],
        key=lambda z: abs_diff(z, y),
    )


def improvement(x, y, z):
    return abs_diff(x, y) - abs_diff(z, y)


def min_diff(a, b):
    sorted_a = sorted(a)
    nearest = [find_nearest(sorted_a, y) for y in b]
    return sum(map(abs_diff, a, b)) - max(map(improvement, a, b, nearest))


print(min_diff([1, 3, 5], [5, 3, 1]))

关于python - 找到两个数组之间的最小可能差，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/65247307/