假设我们有两个长度相同的列表，ls1和 ls2 .例如，我们有
ls1 = [4, 6]
ls2 = [3, 5]
对于 ls1 中的每个元素我们必须将它与 ls2 中的一个元素和一个元素配对，以使得 ls1 中的元素之间的总(绝对)差异的方式和 ls2 中的元素是最小的。一个元素只能匹配一次。在上面的例子中，最优的方式是匹配4。是ls1与 3在ls2 , 和 5在ls1与 6在ls2 , 总差为
(4 - 3) + (6 - 5) = 2
我需要一个程序来返回这两个列表中元素之间的最小总差。列表的长度是任意的，列表中元素的值也是任意的(但它们都是正整数)。
我目前知道使用排列来暴力破解解决方案是一种选择，但我需要的是具有最佳时间和空间复杂度的代码。我听说过动态规划的概念，但我不知道如何在我的案例中实现它。预先感谢您的回复。
附言。这是我当前使用排列的蛮力代码，它在运行时或内存使用方面效率不高:
from itertools import permutations
def minimum_total_difference(ls1, ls2):
length = len(ls1)
possibilities = list(permuations(ls1, length))
out = 10**10
for possibility in possibilities:
out_ = 0
for _ in range(length):
diff = abs(possibility[_] - ls2[_])
out += diff
if out_ < out:
out = out_
return out
最佳答案
可以证明最佳解决方案是对两个列表进行排序并按排序顺序匹配它们的元素。
证明草图:
设一个倒置，即
a匹配到b,c匹配到d和a < c, b > d.我们可以“交换”这些元素:
a->d, c->b.现在a < c, d < b.可以证明这一操作永远不会增加答案(通过考虑a, b, c, d的所有可能的相对值)因此，总有一个最佳匹配，其中两个列表都已排序。
这是实现此解决方案的高效单行代码:
sum(abs(x - y) for x, y in zip(sorted(xs), sorted(ys)))
关于python - 两个列表中元素之间的最小差和，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/41229052/