Блог

Главная - Вопросы по программированию - Найти элемент с максимальным значением меньше другого значения

Найти элемент с максимальным значением меньше другого значения

#c#

#c#

Вопрос:

У меня есть объект с двумя двойными значениями:

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

У меня есть список этих значений, который уже отсортирован по возрастанию. Я хотел бы найти и вернуть индекс объекта в списке с максимальным значением tvd, которое меньше или равно двойному. Как я могу эффективно выполнить эту задачу?

Ответ №1:

Предполагая, что у вас есть 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) where comparer , реализация IComparer<SurveyData> которого сравнивается с помощью TVD. Затем вам нужно будет проверить, было ли возвращаемое значение неотрицательным (найдено точное совпадение) или отрицательным (точное совпадение не найдено, возвращаемое значение является дополнением к тому, где оно будет вставлено).

Разница в сложности составляет между O (n) для простого сканирования или O (log n) для двоичного поиска. Не зная, насколько велик ваш список (или насколько важна производительность), трудно сказать, стоит ли того дополнительная сложность реализации двоичного поиска.

Комментарии:

1. если список находится в порядке возрастания, не так ли values.TakeWhile(data => data.Tvd <= limit).LastOrDefault() ?

2. @ThomasLevesque: Вы абсолютно правы. Я мог бы поклясться, что изначально говорилось, что это в порядке убывания …

3. Похоже TakeUntil , что это из System.Reactive.Linq (и других домотканых реализаций) и TakeWhile находится в ванильном LINQ (т.Е. TakeUntil Нет )? Извините — действительно незначительный, но был выдан «предполагая, что у вас есть LINQ» и не найден TakeUntil .

4. @Ruffin: Упс, да. К счастью, он существует в MoreLINQ — добавит ссылку.

Ответ №2:

Сначала выполните фильтрацию по объектам, которые меньше или равны значению фильтра ( Where ), а затем выберите максимальное из значений этих объектов.

Поскольку он уже находится в порядке возрастания, просто перебирайте набор, пока не найдете значение, большее значения фильтра, затем верните предыдущий индекс.

Ответ №3:

Вот способ сделать это с помощью 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, вероятно, не лучший вариант… простой цикл был бы намного понятнее.