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

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[2]换成A[0]，那么两个数组的差就是：

|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]))

Answer 2

这个 post 错误地回答了问题的一个变体，即允许对 A 中的两个元素进行单个 swap。我想我会留下它自从我开始研究它。

下面是一般的改进可能性。我们可以看到，当我们交换的对具有相反的顺序时（例如，如果 a1 < b1 则 a2 > b2，反之亦然）。仔细观察，我们看到下一个质量是最佳候选交换与第一对的重叠最大。

我们可以有一个 O(n log n) 例程，首先按较低元素对所有给定对进行排序，然后按较低元素的降序处理它们。当我们下降时，为 a < b 的对保留一个顺序统计树，为 b ≤ a 的对保留另一个顺序统计树。按每对中较高的元素对树排序并保留两个装饰：(1) 左子树中看到的最大间隔，以及 (2) 左子树中看到的最低的较低元素。

对于每个处理过的元素，选择（1）对面树中具有相等或更低高元素和最大间隔（对应于第一个树装饰）的对，和（2）对在对面树中具有高于或等于高元素和最低的低元素（对应于第二个树装饰）。

（由于我们按 low 的降序处理对，所以看到的 low 将始终等于或高于当前元素。）

(1)

Original:
     a1-----------b1
                     a2----b2
Total: -----------+----

Swapped:
     a1--------------------b2
                  b1-a2
Total: --------------------+-

Result: worse.

(2)

Original:
     a1-----------b1
                     b2----a2
Total: -----------+----

Swapped:
     a1--------------b2
                  b1-------a2
Total: --------------+-------

Result: worse.

(3)

Original:
     a1-----------b1
             a2------b2
Total: -----------+------

Swapped:
     a1--------------b2
             a2---b1
Total: --------------+---

Result: the same.

(4)

Original:
     a1-----------b1
             b2------a2
Total: -----------+------

Swapped:
     a1------b2
                  b1-a2
Total: ------+-

Result: BETTER.
Improvement: 2 * dist(b2, b1)

(5)

Original:
     a1--------------b1
           a2----b2
Total: --------------+----

Swapped:
     a1----------b2
           a2--------b1
Total: ----------+--------

Result: the same.

(6)

Original:
     a1--------------b1
           b2----a2
Total: --------------+----

Swapped:
     a1----b2
                 a2--b1
Total: ----+--

Result: BETTER.
Improvement: 2 * dist(b2, a2)

(7)

Original:
     a1--------------b1
 b2--------a2
Total: --------------+--------

Swapped:
 b2----a1
           a2--------b1
Total: ----+--------

Result: BETTER.
Improvement: 2 * dist(a1, a2)

(8)

Original:
     a1-----------b1
 b2-------------------a2
Total: -----------+-------------------

Swapped:
 b2--a1
                  b1--a2
Total: --+--

Result: BETTER.
Improvement: 2 * dist(a1, b1)

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

Find the minimum possible difference between two arrays

python

algorithm

complexity-theory