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

Question

我有两个等长的整数列表，每个都没有重复项，我需要根据它们的差异(绝对值)将它们映射到彼此，输出中没有任何内容可以切换以进行总计所有对的差异较小。我能想到的“天真”方法是这样的(在精简的 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);
}

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

Answer 1

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

因此要采取的步骤变成:

1. 对两个输入列表进行排序
2. 在第二个排序列表中找到枢轴元素
3. 将这个枢轴元素与第一个排序列表的第一个元素一起返回
4. 跟踪元素索引向左和向右
5. 按排序顺序迭代第一个列表，返回左边或右边的元素，具体取决于哪个差异最小，并调整左右索引。

如(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++]);
    }
}