將一個列表與另一個列表進行匹配，誤差最小

Question

我有兩個列表，A和B.A最多隻有1000個元素，而B最多隻有100個元素。我想將B的每個元素都匹配到A的一個元素，這樣這些對的絕對差值之和就會最小化。

即我想選擇| B |從A得到不同的索引，並將它們分配給B的索引，使得以下和最小化：sum（abs（A [j] -B [i]），其中| B |，j = index_mapping（i））。

我的第一種方法是：

1. 對於B的每個元素，以計算| B |答：
2. 的最接近元素選擇在一個貪婪的方式對（即誤差最小第一）

用一些簡單的例子播放，很明顯，我的方法是不是最好的。它應該適合我的目的，但我想知道是否有人可以提出更好的方法？

Answer 1

我結束了對這兩個列表的排序，並遍歷它們進行匹配。這對我所做的工作足夠好。

Answer 2

唔......手頭上，想到的第一個想法是，如果你可以對A和B進行排序，那麼一旦你找到A [j]到B [i]的第一個映射，那麼對於B [i +1]，你可以用A [j]而不是A [0]開始你的測試。

例如：

A = [ 23, 34, 38, 52, 67, 68, 77, 80, 84, 95 ] 
B = [ 31, 33, 64, 65, 99 ] 

你開始B [0] = 31，通過臺階，直到找到最接近的匹配，A [1]。由於列表是有序的，所以你知道 B [1]不會匹配小於A [1]的任何東西，所以你可以從那裏開始比較。原來，A [1]仍然是最接近的匹配。在B [2]中，最接近的匹配是A [4]，所以你知道B [3]不會匹配低於A [4]的任何東西，所以不需要通過A [3]搜索A [0]。