2

次のように、.NET2.0のジェネリックリスト<T>から重複を削除するソリューションが用意されています。

List<CaseStudy> caseStudies = CaseStudyDAO.FindCaseStudiesByDate(DateTime.Now.Date, DateTime.Now.Date.AddDays(1));
caseStudies.RemoveAll(
        delegate(CaseStudy c)
        {
            return caseStudies.IndexOf(c) != caseStudies.FindIndex(
                delegate(CaseStudy f) { return c.Str == f.Str; });
        });

私の質問は次のとおりです。

これを行うためのより効率的な方法はありますか？.NET 2.0ソリューションのみ
上記のソリューションの複雑さは何ですか？

ありがとう、
jan2k10

4

2 に答える 2

12

RemoveAllの時間計算量はO（n）です。インデックス作成の時間計算量はO（n）であるため、これはO（n ^ 2）の時間計算量の総計です。スペースの複雑さは、私が思うに、O（1）です。

それを行うためのより効率的な方法はありますか？はい。より多くのスペースを費やすことをいとわないのであれば、O（n）時間計算量でそれを行うことができます。

于 2010-04-07T17:49:30.210 に答える
5

より多くのスペースを使用して満足している場合は、O（n）時間に関するEricのコメントを拡張するために、次のようにします。

Dictionary<string, CaseStudy> lookup = new Dictionary<string, CaseStudy>();
foreach (CaseStudy cs in caseStudies)
{
    lookup[cs.Str] = cs;
}
caseStudies = new List<CaseStudy>(lookup.Values);

いくつかのメモ：

  • これにより、の値が変更caseStudiesされ、新しいリストが参照されます。同じ範囲内に配置したい場合はList<T>、次を使用できます。

    caseStudies.Clear();
caseStudies.AddRange(lookup.Values);

  • これにより、リストの最後の要素がそれぞれ個別のStr値で保持されます。それは、できるだけ短くするためだけのものでした。最初の要素が必要な場合は、次を使用します。

    foreach (CaseStudy cs in caseStudies)
{
    if (!lookup.ContainsKey(cs.Str))
    {
        lookup[cs.Str] = cs;
    }
}
于 2010-04-07T17:55:24.207 に答える