用适当的父对象填充 ICollection<Class>

Question

我有一个 class:

public class MyObject {
    int id;
    int parentId;
    MyObject parentObj;
}

并且我需要用适当的对象填充 parentObj。我需要在性能和简单性方面做到这一点。

所以我有代码：

ICollection<MyObject> Method(ICollection<MyObject> coll)
{
    foreach(var item in coll)
        ...

    return coll;
}

我需要使用此集合中的适当对象填充 parentObj。我认为这个问题的复杂性是 N*log(N).

Answer 1

经典的方法是使用字典。查找操作（检索给定键的值）可以在 O(1) 中实现。这假设一个很好的哈希函数将键映射到查找数组中的一个位置。

使用 .net 中的默认 Dictionary 实现，这将导致此代码。

ICollection<MyObject> Method(ICollection<MyObject> coll)
{
    var lookup = new Dictionary<int, MyObject>();
    foreach (var item in coll)
    {
         lookup.Add(item.id, item);
    }
    foreach (var item in coll)
    {
         item.parentObj = lookup[item.parentId];
    }

    return coll;
}

分配 lookup 会产生内存开销，但运行时间（理论上）为 O(n + n) = O(n)

用适当的父对象填充 ICollection<Class>

Fill ICollection<Class> with proper parent objects

c#

algorithm

icollection