两个列表中元素之间的最小差异之和

Question

假设我们有两个长度相同的列表，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

Answer 1

可以证明，最佳解决方案是对两个列表进行排序，并按排序顺序匹配它们的元素。

证明草图：

1. 设一个a与匹配b，c与d和匹配的反转a < c, b > d。

2. 我们可以“交换”这些元素：a->d, c->b。现在a < c, d < b。可以证明此操作永远不会增加答案（通过考虑的所有可能的相对值a, b, c, d）

3. 因此，总是存在对两个列表都进行排序的最佳匹配。

这是实现此解决方案的有效的一线工具：

sum(abs(x - y) for x, y in zip(sorted(xs), sorted(ys)))