C# - 在没有嵌套循环的情况下匹配列表中 2 项的最佳方法

Question

假设我有一个列表，其中包含电影持续时间的最小值，称为 filmDurations int 类型。
我有一个名为 flightDuration 的 int 参数持续一段时间任何给定航班的分钟数。

我的 objective 是：对于任何给定的 flightDuration，我想匹配我的 filmDurations 中的 2 部电影，它们的总和恰好在飞行 30 分钟后结束。

例如：

电影持续时间 = {130,105,125,140,120}
飞行持续时间 = 280
我的输出：(130 120)

我可以使用嵌套循环来完成。但是没有效果，而且很费时间。

我想更有效地做到这一点。我想使用 Linq，但它仍然是 O(n^2)。

最有效的方法是什么？

编辑：我想澄清一件事。

我想在中找到 filmDurations[i] + filmDurations[j];

电影持续时间[i] + 电影持续时间[j] == fligtDuration - 30

然后说我有很多电影时长。

Answer 1

您可以对所有持续时间进行排序（删除重复项）(O(n log n))，然后遍历它们（直到飞行持续时间长度 -30）。搜索第二部电影的相应长度 (O(log n))。

通过这种方式，您可以在 O(n log n).

中获得所有持续时间对

您还可以使用 HashMap（持续时间 -> 电影）来查找匹配对。

这样就可以避免排序和二分查找。遍历所有持续时间并在地图中查找是否存在持续时间 = (flight-duration -30).

的条目

填充地图需要 O(n) 查找 O(1) 并且您需要迭代所有持续时间。

-> 在所有复杂性中 O(n) 但你失去了找到“几乎匹配的对的可能性，这将很容易使用上述排序列表方法实现）

Answer 2

正如张磊森所说，你可以将所有项目放入字典。这样做之后重写你的等式

filmDurations[i] + filmDurations[j] == fligtDuration - 30

作为

filmDurations[i] == (fligtDuration - 30 - filmDurations[j])

现在，对于 filmDurations 中的每个项目，在字典中搜索 (fligtDuration - 30 - filmDurations[j])。如果找到这样的项目，您就有解决方案。

下一个代码实现这个概念

public class IndicesSearch
{
    private readonly List<int> filmDurations;
    private readonly Dictionary<int, int> valuesAndIndices;

    public IndicesSearch(List<int> filmDurations)
    {
        this.filmDurations = filmDurations;

        // preprocessing O(n)
        valuesAndIndices = filmDurations
            .Select((v, i) => new {value = v, index = i})
            .ToDictionary(k => k.value, v => v.index);
    }

    public (int, int) FindIndices(
        int flightDuration,
        int diff = 30)
    {
        // search, also O(n)
        for (var i = 0; i < filmDurations.Count; ++i)
        {
            var filmDuration = filmDurations[i];
            var toFind = flightDuration - filmDuration  - diff;
            if (valuesAndIndices.TryGetValue(toFind, out var j))
                return (i, j);
        }

        // no solution found
        return (-1, -1); // or throw exception
    }
}

C# - 在没有嵌套循环的情况下匹配列表中 2 项的最佳方法

C# - Best Way to Match 2 items from a List Without Nested Loops

c#

algorithm

list

matching