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

Question

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

9

我很难想出一个高效的算法来执行以下任务：

给定两个长度相等的数组 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)（暴力）解决这个问题，但很难想到更高效的方法。

谢谢！

- anoooon

2

排序将使其变为nlogn。会考虑是否可能为n。 - Shridhar R Kulkarni

计算您发布的“diff”方程。检查A中哪个元素最接近“diff”。相应更改。我还没有想到完全的证明，但这应该可以帮助您在n内解决它。 - Shridhar R Kulkarni

只使用加法/减法/比较操作，你不可能得到一个O(n log n)时间复杂度的算法，因为这里存在元素不同性问题的约束。 - David Eisenstat

是的，有一个类似于@ShridharRKulkarni建议的O(n log n)算法。 - David Eisenstat

@DavidEisenstat 你有任何想法它可能如何工作吗？我的原始想法是对数组B进行排序，然后对A中的每个元素在B上执行二进制搜索。您将执行此操作以查找在B中给您提供A中每个元素的最小可能总和的值，跟踪将使此总和的原始数组中的索引(i，j)。找到最小总和后，您可以简单地用i替换a[j]。但是，如果B具有重复值，则不起作用。 - anoooon

显示剩余2条评论

2个回答

0

这篇文章错误地回答了一个问题的变体，即允许在A中交换两个元素。我认为我会把它留下来，因为我已经在上面工作了。

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

我们可以通过首先按其较低元素对所有给定的对进行排序，然后按较低元素的降序处理它们来拥有一个O(n log n)例程。当我们下降时，为a < b的对保留一个顺序统计树，为b ≤ a的对保留另一个顺序统计树。按每对的较高元素对树进行排序，并保持两个装饰：（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)

- גלעד ברקן

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- David Eisenstat · Accepted Answer

我将采用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]))