他のリストから一番高いランクのアイテムを見つけよう

Question

私は変数に格納されている最高ランクのアイテムのリストを持っていますトップリスト。

は、その後、私は、私は、変数currentListに格納アイテム

の現在のリストを持っている目標は、最高のほんにランクされてcurrentListの要素を見つけることです。

[TestMethod] 
public void MethodName14() { 
    var topList = new List<string>() {"AB", "DC", "ZG"}; // ordered by highest rank 
    var currentList = new List<string> {"ZG", "DC"}; 
    var actual = ReturnTop(currentList, topList); 
    Assert.Equal("DC", actual); // because DC is in index 2 and ZG is in index 3 
} 

private string ReturnTop(List<string> currentList, List<string> topList) { 
    string result = null; 
    int index = 0; 
    foreach (var current in currentList) { 
     var lookupedCurrentIndex = topList.FindIndex(a => a == current); 
     if (index == 0) { 
      result = topList[index]; 
      index = lookupedCurrentIndex; 
     } else { 
      if (lookupedCurrentIndex < index) { 
       index = lookupedCurrentIndex; 
       result = topList[index]; 
      } 
     } 
    } 
    return result; 
} 

私のメソッドReturnTopは遅すぎるので、O（n²）です。私たちはもっとうまくできますか？

Answer 1

現在の実装はO（N * T）です.Nはクエリリスト内のアイテムの数で、Tはトップリスト内のアイテムの数です。スペースの使用ではO（1）です。

O（N）にスペースを使用しても構わない場合は、クエリワードからハッシュセットを作成し、最初の単語をtopListで検索することで、O（N + T）次のように、クエリの単語のいずれかに一致：

var knownWords = new HashSet<string>(currentList); 
return topList.FirstOrDefault(w => knownWords.Contains(w)); 

がknownWordsはO（N）時間とO（N）スペースをとり構築。 knownWordsに存在する最も早い項目のtopListを検索すると、ハッシュセットルックアップがO（1）なので、O（T）時間とO（1）時間がかかります。一番上の項目の検索以下のソリューションで

これはさらにこれに短縮することができます（、Slaiをありがとう！）

return topList.Intersect(currentList).FirstOrDefault(); 

Answer 2

var topList = new List<string>() {"AB", "DC", "ZG"}; // ordered by highest rank 
var currentList = new List<string> {"ZG", "DC"}; 

var bestItem = currentList.OrderBy(item => topList.FindIndex(a => a == item)).FirstOrDefault(); 

Console.WriteLine(bestItem); 

http://csharppad.com/gist/b6f3b41afb86018c6f81284cc4ae22b5

Answer 3

場所（O（N + M）がかかりますNはトップリストアイテムの量であり、Mは現在のリストの量である）O（2N）としてカウントすることができる。

topListのすべてのアイテムを一度ループする.crea辞書をつづる。
最小インデックスを持つアイテムを検索するためにcurrentのすべてのアイテムを一度ループします。

private string ReturnTop(IEnumerable<string> current, IEnumerable<string> topList) 
    { 
     var topMap = topList.Select((value, index) => new {Value = value, Index = index}) 
          .ToDictionary(item => item.Value, item => item.Index); 

     string minItem = null; 
     int minPosition = topMap.Count; 
     foreach (var item in current) 
     { 
      var currentPosition = topMap[item]; 
      if (currentPosition == 0) 
      { 
       return item; 
      } 

      if (currentPosition < minPosition) 
      { 
       minPosition = currentPosition; 
       minItem = item; 
      } 
     } 

     return minItem; 
    }