有没有一种有效的算法可以做到这一点？

Question

我有两个等长的整数列表，每个都没有重复项，我需要根据它们的差异（绝对值）将它们相互映射，输出中没有任何内容可以切换所有对的总差异较小。我能想到的 'naive' 方法运行是这样的（在精简的 C# 中，但我认为它很容易获得）：

Dictionary<int, int> output;
List<int> list1, list2;
while(!list1.Empty) //While we haven't arranged all the pairs
{
    int bestDistance = Int32.MaxValue; //best distance between numbers so far
    int bestFirst, bestSecond; //best numbers so far
    foreach(int i in list1)
    {
        foreach(int j in list2)
        {
            int distance = Math.Abs(i - j);
            //if the distance is better than the best so far, make it the new best
            if(distance < bestDistance)
            {
                bestDistance = distance;
                bestFirst = i;
                bestSecond = j;
            }
        }
    }
    output[bestFirst] = bestSecond; //add the best to dictionary
    list1.Remove(bestFirst); //remove it from the lists
    list2.Remove(bestSecond);
}

本质上，它只是找到最好的一对，将其删除，然后重复直到完成。但是这个运行s 以立方时间表示，如果我没看错的话，对于大型列表来说会花费非常长的时间。有没有更快的方法来做到这一点？

Answer 1

这不像我最初的预感所建议的那样微不足道。保持此 O(N log(N)) 的关键是使用排序列表，并在第二个排序列表中搜索与第一个排序列表中的第一个元素差异最小的 "pivot" 元素。

因此要采取的步骤变为：

对两个输入列表进行排序
在第二个排序列表中找到主元元素
Return 这个枢轴元素连同第一个排序列表的第一个元素
跟踪元素索引左侧到枢轴和右侧的元素索引
按排序顺序迭代第一个列表，返回左边或右边的元素，具体取决于哪个差异最小，并调整左右索引。

如（c# 示例）：

public static IEnumerable<KeyValuePair<int, int>> FindSmallestDistances(List<int> first, List<int> second)
{
    Debug.Assert(first.Count == second.Count); // precondition.

    // sort the input: O(N log(N)).
    first.Sort();
    second.Sort();

    // determine pivot: O(N).
    var min_first = first[0];
    var smallest_abs_dif = Math.Abs(second[0] - min_first);
    var pivot_ndx = 0;
    for (int i = 1; i < second.Count; i++)
    {
        var abs_dif = Math.Abs(second[i] - min_first);
        if (abs_dif < smallest_abs_dif)
        {
            smallest_abs_dif = abs_dif;
            pivot_ndx = i;
        }
    };

    // return the first one.
    yield return new KeyValuePair<int, int>(min_first, second[pivot_ndx]);

    // Iterate the rest: O(N)
    var left = pivot_ndx - 1;
    var right = pivot_ndx + 1;
    for (var i = 1; i < first.Count; i++)
    {
        if (left >= 0)
        {
            if (right < first.Count && Math.Abs(first[i] - second[left]) > Math.Abs(first[i] - second[right]))
                yield return new KeyValuePair<int, int>(first[i], second[right++]);
            else
                yield return new KeyValuePair<int, int>(first[i], second[left--]);
        }
        else
            yield return new KeyValuePair<int, int>(first[i], second[right++]);
    }
}

有没有一种有效的算法可以做到这一点？

Is there an efficient algorithm that could do this?

algorithm

language-agnostic