從另一個列表中查找列表中排名最高的項目

我有一個商品列表已按最高排名排序，我在變量topList中存儲。從另一個列表中查找列表中排名最高的項目

然後我有我存儲在變量currentList

的目標是找到誰是排名最高的topList 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²）。我們可以做得更好嗎？

來源

2016-12-31 Gui

您當前的實現是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）的空間。因爲散列集合查找是O（1），所以在knownWords中存在的最早的項目搜索topList需要O（T）時間和O（1）空間。

這可以進一步簡化爲這個（感謝你，Slai！）

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

來源

2016-12-31 22:39:10 dasblinkenlight

好像它可以縮短到'topList.Intersect（currentList）.FirstOrDefault（）'https://referencesource.microsoft.com/#System.Core/System/Linq/Enumerable.cs,ae06318d1f5fb355 – Slai

@Slai你說得對，謝謝！ – dasblinkenlight

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

來源

2016-12-31 22:41:55

儘管這個實現比OP的實現要短得多，但'OrderBy'使用線性搜索進行項目比較，所以這個算法是O（T * N * LogN），即比OP的O（T * N）算法漸近地稍差。 – dasblinkenlight

我懷疑有腥味;） –

低於頂部項目的搜索將採取O（N + M）解決方案（其中N是topList項目的數量，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; 
    }

來源

2016-12-31 23:39:22 Fabio

從另一個列表中查找列表中排名最高的項目

回答

相關問題