my_list = [20, 1, 9, 5, 10, 3, 4, 2, 11, 21, 2]

max2 = 0
max1 = 0
for i in my_list:
    if i > max1:
        max1 = i
    elif max2 < i < max1:
        max2 = i

print(f'max1: {max1}; max2: {max2}')
max1: 21; max2: 11

В Python используйте heapq.nlargest . Это наиболее гибкий подход на тот случай, если вы когда-нибудь захотите обработать не только два верхних элемента.

Вот пример.

>>> import heapq
>>> import random
>>> x = range(100000)
>>> random.shuffle(x)
>>> heapq.nlargest(2, x)
[99999, 99998]

Документация: http://docs.python.org/library/heapq.html#heapq.nlargest

Итерация по всему списку - единственный способ сделать это без сортировки.

Вы просматриваете список, поддерживая переменные, которые содержат значение самого высокого и второго по величине элемента, обнаруженных до сих пор. Каждый обнаруженный новый элемент будет заменять тот из двух, над которым новый элемент находится выше (если таковой имеется).

Без сортировки списка единственный способ сделать это - это перебрать весь список и сохранить два старших числа. Думаю, тебе лучше отсортировать список.

Второй самый высокий элемент - это довольно простой случай, но для k-го самого высокого элемента вам нужен алгоритм выбора . Эта страница довольно подробна, так что, вероятно, лучше просто ее прочитать.

Это будет работать, но я не знаю, хотите ли вы сохранить элементы в списке:

max1 = max(myList)
myList.remove(max1)
max2 = max(myList)

Если да, то можно сделать так:

max1 = max(myList)
idx1 = myList.index(max1)
myList.pop(idx1)

max2 = max(myList)
myList.insert(idx1,max1)

Лучшее время, на которое вы можете рассчитывать - линейное, так как вам нужно как минимум просмотреть все элементы.

Вот мой псевдокод для решения проблемы:

//assume list has at least 2 elements
(max, nextMax) = if (list[0] > list[1])
                 then (list[0], list[1])
                 else (list[1], list[0])

for (2 <= i < length) {
    (max, nextMax) = if       (max < list[i])     => (list[i], max)
                     elseif   (nextMax < list[i]) => (max, list[i])
                     else     (no change)         => (max, nextMax)
}

return (max, nextMax)

"2 самых высоких" невозможно; только один элемент может быть "самым высоким". Возможно, вы имеете в виду "2 наивысших". В любом случае, вам нужно сказать, что делать, когда список содержит дубликаты. Что вы хотите получить из [8, 9, 10, 10]: (10, 9) или (10, 10)? Если ваш ответ - (10, 10), рассмотрите возможность ввода [8, 9, 10, 10, 10]. Что вы собираетесь делать с "двумя высшими", когда получите их? Пожалуйста, отредактируйте свой вопрос, чтобы дать это указание.

Тем временем, вот ответ, который использует первый подход (два уникальных значения):

largest = max(inlist)
second_largest = max(item for item in inlist if item < largest)

Вы должны добавить защиту от менее чем 2 уникальных значений в списке.

Ответ JacobM - это абсолютно правильный путь. Однако при реализации того, что он описал, следует помнить о нескольких вещах. Вот небольшое руководство по игре, которое поможет вам разобраться в более сложных частях решения этой проблемы.

Если этот код предназначен для производственного использования, используйте один из наиболее эффективных / кратких из перечисленных ответов. Этот ответ предназначен для новичков в программировании.

Идея

Идея проста.

• Сохраните две переменные: наибольшая и вторая_ наибольшая .
• Просмотрите список.
  • Если элемент больше, чем наибольший , присвойте ему наибольший .
  • Если элемент больше second_largest , но меньше large , присвойте ему second_largest .

Начало работы

Приступим.

def two_largest(inlist):
    """Return the two largest items in the sequence. The sequence must
    contain at least two items."""
    for item in inlist:
        if item > largest:
            largest = item
        elif largest > item > second_largest:
            second_largest = item
    # Return the results as a tuple
    return largest, second_largest

# If we run this script, it will should find the two largest items and
# print those
if __name__ == "__main__":
    inlist = [3, 2, 1]
    print two_largest(inlist)

Хорошо, теперь у нас есть ответ JacobM в виде функции Python. Что происходит, когда мы пытаемся запустить его?

Traceback (most recent call last):
  File "twol.py", line 10, in <module>
    print two_largest(inlist)
  File "twol.py", line 3, in two_largest
    if item > largest:
UnboundLocalError: local variable 'largest' referenced before assignment

Очевидно, нам нужно установить наибольшее , прежде чем мы начнем цикл. Это, вероятно, означает, что мы также должны установить second_largest .

Инициализация переменных

Давайте установим наибольший и second_largest равным 0.

def two_largest(inlist):
    """Return the two largest items in the sequence. The sequence must
    contain at least two items."""
    largest = 0 # NEW!
    second_largest = 0 # NEW!
    for item in inlist:
        if item > largest:
            largest = item
        elif largest > item > second_largest:
            second_largest = item
    # Return the results as a tuple
    return largest, second_largest

# If we run this script, it will should find the two largest items and
# print those
if __name__ == "__main__":
    inlist = [3, 2, 1]
    print two_largest(inlist)

Хорошо. Давай запустим.

(3, 2)

Отлично! Теперь давайте протестируем, когда inlist будет [1, 2, 3]

    inlist = [1, 2, 3] # CHANGED!

Давайте попробуем.

(3, 0)

... Ой-ой.

Исправление логики

Наибольшее значение (3) кажется правильным. Однако второе по величине значение совершенно неверно. Что происходит?

Давайте разберемся, что делает функция.

• Когда мы начинаем, наибольший равен 0 и second_largest также равен 0.
• Первый элемент в списке, который мы смотрим, равен 1, поэтому наибольший ] становится 1.
• Следующий элемент равен 2, поэтому наибольший становится 2.

Но как насчет second_largest ?

Когда мы присваиваем новое значение ] наибольшее , наибольшее значение фактически становится вторым по величине. Нам нужно показать это в коде.

def two_largest(inlist):
    """Return the two largest items in the sequence. The sequence must
    contain at least two items."""
    largest = 0
    second_largest = 0
    for item in inlist:
        if item > largest:
            second_largest = largest # NEW!
            largest = item
        elif largest > item > second_largest:
            second_largest = item
    # Return the results as a tuple
    return largest, second_largest

# If we run this script, it will should find the two largest items and
# print those
if __name__ == "__main__":
    inlist = [1, 2, 3]
    print two_largest(inlist)

Давайте запустим.

(3, 2)

Фантастика.

Инициализация переменных, часть 2

Теперь давайте попробуем это со списком отрицательных чисел.

    inlist = [-1, -2, -3] # CHANGED!

Давайте запустим.

(0, 0)

Это совсем не так.Откуда взялись эти нули?

Оказывается, начальные значения для наибольший и second_largest на самом деле были больше, чем все элементы в списке. Первое, что вы могли бы подумать, это установить large и second_largest на самые низкие значения, возможные в Python. К сожалению, у Python нет минимально возможного значения. Это означает, что даже если вы установите для них оба значения -1 000 000 000 000 000 000, у вас может быть список значений меньшего, чем это.

Так что лучше всего делать? Попробуем установить наибольший и второй_размер для первого и второго элементов в списке. Затем, чтобы избежать двойного подсчета любых элементов в списке, мы смотрим только на часть списка после второго элемента.

def two_largest(inlist):
    """Return the two largest items in the sequence. The sequence must
    contain at least two items."""
    largest = inlist[0] # CHANGED!
    second_largest = inlist[1] # CHANGED!
    # Only look at the part of inlist starting with item 2
    for item in inlist[2:]: # CHANGED!
        if item > largest:
            second_largest = largest
            largest = item
        elif largest > item > second_largest:
            second_largest = item
    # Return the results as a tuple
    return largest, second_largest

# If we run this script, it will should find the two largest items and
# print those
if __name__ == "__main__":
    inlist = [-1, -2, -3]
    print two_largest(inlist)

Давайте запустим.

(-1, -2)

Отлично! Попробуем с другим списком отрицательных чисел.

    inlist = [-3, -2, -1] # CHANGED!

Давайте запустим.

(-1, -3)

Подождите, что?

Инициализация переменных, часть 3

Давайте еще раз рассмотрим нашу логику.

• наибольший установлен на -3
• second_largest установлен на -2

Подождите прямо сейчас. Это уже кажется неправильным. -2 больше -3. Это то, что вызвало проблему? Давай продолжим.

• наибольший установлен в -1; second_largest установлено на старое значение large , которое равно -3

Да, похоже, это проблема. Нам необходимо убедиться, что наибольшее значение и второе_значение установлены правильно.

def two_largest(inlist):
    """Return the two largest items in the sequence. The sequence must
    contain at least two items."""
    if inlist[0] > inlist[1]: # NEW
        largest = inlist[0]
        second_largest = inlist[1]
    else: # NEW
        largest = inlist[1] # NEW
        second_largest = inlist[0] # NEW
    # Only look at the part of inlist starting with item 2
    for item in inlist[2:]:
        if item > largest:
            second_largest = largest
            largest = item
        elif largest > item > second_largest:
            second_largest = item
    # Return the results as a tuple
    return largest, second_largest

# If we run this script, it will should find the two largest items and
# print those
if __name__ == "__main__":
    inlist = [-3, -2, -1]
    print two_largest(inlist)

Давайте запустим.

(-1, -2)

Отлично.

Заключение

Итак, вот код, хорошо прокомментированный и отформатированный.В нем также были устранены все ошибки, которые я мог найти. Наслаждаться.

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

Эффективность

Не очень эффективна. Но для большинства целей это должно быть нормально: на моем компьютере (Core 2 Duo) список из 100 000 элементов может быть обработан за 0,27 секунды (с использованием timeit , в среднем за 100 запусков).

Действительно хороший способ - использовать heapq . Заполните массив (O (n)), затем просто вставьте много элементов, которые вам нужны (log (n)). (Однажды видел этот вопрос в интервью, хороший вопрос, о котором стоит помнить.)