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

Question

我有一个类：

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）