Получить второе по величине число в списке за линейное время
Я изучаю Python, и простые способы обработки списков представлены как преимущество. Иногда это так, но посмотрите на это:
Очень простой и быстрый способ получить второе по величине число из списка. За исключением того, что простая обработка списка помогает написать программу, которая дважды просматривает список, чтобы найти наибольшее, а затем второе место. Это также разрушительно — мне нужно две копии данных, если я хочу сохранить оригинал. Нам нужно:
Который проходит по списку только один раз, но не является кратким и понятным, как предыдущее решение.
Итак: есть ли способ, в таких случаях, чтобы иметь оба? Четкость первой версии, но единственная пробежка второй?
23 ответа
Поскольку у @OscarLopez и у меня разные мнения о том, что означает второй по величине, я опубликую код в соответствии с моей интерпретацией и в соответствии с первым алгоритмом, предоставленным спрашивающим.
(Примечание: здесь используется отрицательная бесконечность вместо None , поскольку None имеет разное поведение сортировки в Python 2 и 3 — см. Python — Найти второе наименьшее число; проверка количества элементов в numbers гарантирует, что отрицательная бесконечность не будет возвращена, когда фактический ответ не определен.)
Если максимум встречается несколько раз, он также может быть вторым по величине. Еще одна особенность этого подхода заключается в том, что он работает правильно, если в нем меньше двух элементов; тогда нет второго по величине.
Запуск тех же тестов:
Обновить
Я реструктурировал условия, чтобы кардинально улучшить производительность; почти на 100% в моем тестировании на случайные числа. Причина этого заключается в том, что в исходной версии elif всегда оценивался в вероятном случае, когда следующее число не является наибольшим в списке. Другими словами, практически для каждого числа в списке было сделано два сравнения, тогда как одного сравнения в основном достаточно — если число не больше второго по величине, оно также не больше самого большого.
Зачем усложнять сценарий? Это очень просто и прямо
- Конвертировать список для установки — удаляет дубликаты
- Преобразовать набор в список снова — что дает список в порядке возрастания
Максимальное значение путем сравнения каждого из max_item. В первом случае, если каждый раз, когда значение max_item изменяется, оно возвращает свое предыдущее значение в second_max. Чтобы крепко соединить две секунды, если обеспечивает границу
Попробуйте следующее решение: это O(n) , и оно будет хранить и возвращать второе наибольшее число в переменной second . ОБНОВЛЕНИЕ . Я настроил код для работы с Python 3, поскольку теперь арифметические сравнения с None недопустимы.
Обратите внимание: если все элементы в numbers равны или если numbers пуст или содержит один элемент, переменная second будет иметь значение None — это правильно, так как в этих случаях нет «второго по величине» элемента.
Остерегайтесь : это находит значение «второго максимума», если есть более одного значения, которое является «первым максимумом», все они будут рассматриваться как один и тот же максимум — в моем определении, в списке, таком как это: [10, 7, 10] правильный ответ: 7 .
Найти два максимальных значения списка
Сравнить два списка в python, найти отличающиеся значения
У меня есть 2 переменные, в которых хранятся следующие значения: var1 = >, <2: >, <4: >] var2.
Найти два максимальных значения в массиве
Собственно, не получается реализовать нахождение второго максимального значения: // Найдти 2.
Найти первые два минимальных и максимальных значения элементов массива
Выбрать алгоритм, составить его блок-схему и программу, в ко- торой: 1) вычислить в точках xi = a.
Сообщение от eaa
За один проход цикла найти два максимальных значения среди всех данных и удалить их
Задача: За один проход цикла найти два максимальных значения среди всех данных и удалить их. Затем.
Вывод два максимальных значения
Я только учусь,много еще не понимаю. У меня есть программа ,которая ищет коэффициенты при которых.
Одномерный массив. Найти в нем два максимальных и два минимальных элемента.
решите пожалуйста задачу)))))): дан одномерный массив. надо найти в этом массиве два.
Последовательность целых чисел. Найти два минимальных / два максимальных элемента
Дана последовательность целых чисел a1,a2. an, где n=> 3. Найти: а) два максимальных элемента.
Найти три максимальных элемента числового списка за время O(n), где n-длина списка
Мое решение: (defun 3max (lst &optional (m1 (car lst)) (m2 (car lst)) (m3 (car lst))) .
Как правильно решить задачу по поиску двух максимальных чисел в списке?
Наткнулся на задачу: найти два максимальных из списка чисел и найти их сумму. Пришла только такая простая мысль:
Но в списке же могут быть и текстовые данные.
Как правильно и элегантно решить?
- Вопрос задан более трёх лет назад
- 5963 просмотра
- Вконтакте
Вариант без сортировки:
- Вконтакте
я так и не понял, зачем в ответах все очищают список от нечисловых данных. в задаче четко говорится: «найти два максимальных из списка чисел и найти их сумму». то, что данные могут быть нечисловыми, автор, похоже, откуда-то из головы взял.