查找项目有了最大值小于另一个值

class SurveyData(){ double md; double tvd; }

我有一个已经升序排列这些值的列表。我想查找并返回列表中对象的索引，其中最大tvd值小于或等于double。我怎样才能有效地完成这项任务？

2011-10-13 John

假设你有LINQ和乐于使用TakeUntil从MoreLINQ，我怀疑你想：

var maxCappedValue = values.TakeUntil(data => data.Tvd >= limit) 
          .LastOrDefault();

，将让你的第一个实际值，而不是指数，但你总是做：

var maxCappedPair = values.Select((value, index) => new { value, index }) 
          .TakeUntil(pair => pair.value.Tvd >= limit) 
          .LastOrDefault();

索引/值对。在两种情况下，如果所有值均超出限制，结果将为空。

当然，使用二分查找会更高效 - 但也稍微复杂一些。您可以使用极限TVD创建一个“虚拟”值，然后使用List<T>.BinarySearch(dummy, comparer)，其中comparer将执行通过TVD进行比较的IComparer<SurveyData>。然后，您需要检查返回值是否为非负数（完全匹配找到）或负数（完全匹配未找到，返回值是插入将插入的补码）。

复杂度的差异在简单扫描的O（n）或二进制搜索的O（log n）之间。不知道列表有多大（或者性能有多重要），很难指出二进制搜索的额外实现复杂性是否值得。

来源

2011-10-13 15:52:59

如果列表按升序排列，不应该是'values.TakeWhile（data => data.Tvd <= limit）.LastOrDefault（）'？ –

@ThomasLevesque：你说的没错。我可以发誓，它原来说它是按降序排列的...... –

看起来'TakeUntil'来自'System.Reactive.Linq'（和其他的homespun实现），而'TakeWhile'在香草LINQ（即，['TakeUntil'不是]（http://msdn.microsoft.com/en-us/library/vstudio/system.linq.enumerable_methods%28v=vs.100%29.aspx））？对不起 - 很小，但被*“假设你有LINQ”*而没有找到'TakeUntil'。 – ruffin

先对小于或等于过滤器值（Where）的对象进行过滤，然后选择这些对象值的最大值。

由于它已经以升序排列，只需遍历该集合，直到找到大于过滤器值的值，然后返回上一个索引。

来源

2011-10-13 15:51:49 ravuya

这里是一种使用LINQ做到这一点：

int indexOfMax = 
    data.Select((d, i) => new { Data = d, Index = i }) // associate an index with each item 
     .Where(item => item.Data.tvd <= maxValue) // filter values greater than maxValue 
     .Aggregate(// Compute the max 
      new { MaxValue = double.MinValue, Index = -1 }, 
      (acc, item) => item.Data.tvd <= acc.MaxValue ? acc : new { MaxValue = item.Data.tvd, Index = item.Index }, 
      acc => acc.Index);

但是，在这样的情况下，LINQ的可能不是最好的选择......一个简单的循环会更清晰。

来源

2011-10-13 15:56:17

查找项目有了最大值小于另一个值

回答

相关问题