两个列表中术语差异的最小求和
假设我有两个python列表，如下所示：
30,400,500
我想找出元素之间的最小(绝对值)差之和。在这种情况下，很容易：(55-30) + (400-396) + (500-478) = 51。
但是，当列表中没有相同数量的元素时，我该如何有效地完成这个任务呢？例如：
第1组： list1 = 30,400,500 list2 = 412,489
或者即使它是
第二组 list1 = 30,400,500 list2 = 24,563
最后，
第3组 list1 = 30，50 list2 = 20，31，90
对于第1组，答案是(412-400) + (500-489) = 23。
对于第二组，答案是(30-24) + (563-500) = 69。
对于第三组，答案是(30-20) + (50-31) =29。
我不能用元素来比较。在集合1中，通过将list1的第二个元素与list2的第一个元素以及list1的第三个元素与list2的第二个元素进行比较，得到最小差的总和。在集合2中，通过将list1的第一个元素与list2的第一个元素以及list1的第三个元素与list2的第二个元素进行比较，得到最小差的总和。
任何帮助都是非常感谢的。
其他一些信息：
- 列表的长度永远不会超过其他列表的2倍，但是对于list1是更大的列表还是list2是更大的列表，没有任何限制。
- 列表将按顺序排列。
- 短列表中的所有元素必须至少使用一次。
回答 6
Stack Overflow用户
发布于 2018-07-18 20:24:11
为了确保得到正确的答案，我将使用二部加权匹配，其中每对之间的abs是权重。这将避免基于排序的方法的所有缺陷，例如
list1=[30, 50], list2=[20, 31, 90], ans= 29大多数直觉算法会将30和31配对。(给予第41笔款项)
下面是一种使用linear_sum_assignment的解决方案
import numpy as np
from scipy.optimize import linear_sum_assignment
def min_diff_sum(list1, list2):
arr1 = np.asanyarray(list1)
arr2 = np.asanyarray(list2)
cost_matrix = np.abs(arr1-arr2[:, None])
pairs = linear_sum_assignment(cost_matrix)
return np.sum(cost_matrix[pairs])这应该总是给出正确的结果。
In [45]: min_diff_sum([30, 400, 500], [412, 489])
Out[45]: 23
In [46]: min_diff_sum([30, 400, 500], [24, 563])
Out[46]: 69Stack Overflow用户
发布于 2018-07-18 19:46:47
解决此问题的一种方法是首先选择较小的列表。从较小的列表中逐个获取数字，并搜索最小绝对差(同时跟踪索引)，一旦找到最小绝对差，将其添加到最终的sum中，并从更大的列表中删除该元素，这样您就不会再考虑这个问题了。
此解为O(NM)。假设list1和list2的列表大小约束分别为N、M。您可以优化O(NLogN + NLogM)的解决方案，方法是对O(NLogN)中较大的列表进行排序，并使用二进制搜索找到最小绝对差。
Stack Overflow用户
发布于 2018-07-18 19:46:58
您可以使用bisect模块：
import bisect
list1 = [30, 400, 500]
list2 = [412, 489]
list1.sort() # list1 must be sorted
result = []
for el in sorted(list2): # walk through the elements in sorted order
pos = bisect.bisect_left(list1, el) # find the closest elements
if pos >= len(list1): # el is bigger than last element, use it
pos -= 1
elif pos > 0 and abs(list1[pos-1] - el) <= abs(list1[pos] - el):
pos = pos - 1
result.append(abs(list1[pos] - el))
del list1[pos]
print(result)[12, 11]中的结果(即[412-400, 500-489])
如果使用list2 = [24, 563]，则会得到[6, 63] (即[30-24, 563-500])。
https://stackoverflow.com/questions/51409756
复制相似问题
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号