从另一个列表中查找列表中排名最高的项目

我有一个商品列表已按最高排名排序，我在变量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

从另一个列表中查找列表中排名最高的项目

回答

相关问题