假设我们有两个长度相同的列表,分别为
我需要一个程序来返回这两个列表中元素之间的最小总差。这两个列表的长度是任意的,列表中元素的值也是任意的(但它们都是正整数)。
我知道使用排列来暴力解决问题是一种选择,但我需要一个具有最佳时间和空间复杂度的代码。我听说过动态规划的概念,但我不知道如何在我的情况下实现它。提前感谢回复。
附带我的当前暴力代码,它使用排列,但运行时效率和内存使用效率都不高:
ls1
和ls2
。例如:ls1 = [4, 6]
ls2 = [3, 5]
对于ls1
中的每个元素,我们必须将其与ls2
中的一个元素配对,使得ls1
中的元素与ls2
中的元素之间的(绝对值)差的总和最小。每个元素只能匹配一次。在上面的例子中,最优的方式是将ls1
中的4
与ls2
中的3
匹配,将ls1
中的5
与ls2
中的6
匹配,这样可以得到总差:
(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
n
索引之间的最小差异或整体上的最小差异,即两个列表中任意元素之间的差异? - Moinuddin Quadri