找到最大值小于另一个值的物品

本文关键字：另一个 最大值 小于 | 更新日期: 2023-09-27 18:11:23

我有一个双精度对象:

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

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

找到最大值小于另一个值的物品

假设您已经有了LINQ并且很乐意使用MoreLINQ的TakeUntil，我怀疑您想要:

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将是IComparer<SurveyData>的实现，通过TVD进行比较。然后，您需要检查返回值是非负的(找到了精确匹配)还是负的(没有找到精确匹配，返回值是将插入位置的补码)。

复杂度的差异是简单扫描的O(n)和二分搜索的O(log n)。在不知道列表有多大(或者性能有多重要)的情况下，很难判断二进制搜索的额外实现复杂性是否值得。

首先筛选小于或等于筛选值(Where)的对象，然后选择这些对象值中的最大值。

因为它已经是升序的，所以只需遍历集合，直到找到一个大于过滤值的值，然后返回前一个索引。

下面是使用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可能不是最好的选择…一个简单的循环会更清晰。

相关文章：