寻找两个数组之间的最小可能差异
我很难找到一种有效的算法来执行以下任务：
给定两个长度相同的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替换A2，那么这两个数组之间的区别是：
|1-5| + |3-3| + |1-1| = 4这是两个数组之间可能存在的最小差异。用A中的另一个元素代替A中的元素不会使A和B之间的差异更小。
我该如何解决这个问题呢？我知道如何用O(n^2) (蛮力)来解决这个问题，但努力想出一种更有效的方法。
谢谢!
回答 2
Stack Overflow用户
发布于 2020-12-11 18:39:46
我将实现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]))Stack Overflow用户
发布于 2020-12-12 05:25:11
这篇文章错误地回答了这个问题的一个变体，那就是允许A中的两个元素进行一次交换，我想我应该放弃它，因为我一直在研究它。
以下是改进的一般可能性。我们可以看到，当我们交换的对具有相反的顺序时(例如，如果a1 < b1那么a2 > b2，反之亦然)，就会发生改进。更仔细地看，我们看到的下一个质量是最好的候选交换与第一对有最大的重叠。
我们可以有一个O(n log n)例程，首先将所有给定的对按其较低的元素排序，然后按较低元素的降序处理它们。当我们下降时，对a < b的对保持一个顺序统计树，对于b ≤ a的对保持另一个顺序统计树。根据每对树的较高元素排列树，并保留两个装饰：(1)左子树中的最大间隔，(2)左子树中最低的下元素。
对于每个处理后的元素，选择(1)在相对树中具有相等或较低元素的对对和最大间隔(对应于第一树装饰)之间的较大重叠；(2)在相对树中具有高于或等于高元素和最低下元素(对应于第二树装饰)之间的较大重叠。
(由于我们正在按low的降序处理这些对，可见的lows总是等于或高于当前元素。)
(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)https://stackoverflow.com/questions/65247307
复制相似问题
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号