找出两个数组之间可能的最小差异

Question

我正在努力找出一种有效的算法来执行以下任务：

给定两个长度相等的数组 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[0] 替换 A[2]，那么两个数组的区别是：

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

这是两个阵列之间可能的最小差异。用 A 中的另一个元素替换 A 中的元素不会导致 A 和 B 之间的差异更小。

我将如何解决这个问题？我知道如何解决 O(n^2)（蛮力）中的问题，但正在努力找出更有效的方法。

谢谢！

Answer 1

我将实施 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]))