Получить два самых высоких элемента из списка, содержащего 100 000 целых чисел

Question

Как можно извлечь два самых высоких элемента из списка, содержащего 100 000 целых чисел, без предварительной сортировки всего списка?

Answer 1

В 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

Answer 2

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

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

Идея

Идея проста.

• Оставьте две переменные: largest и second_largest.
• Перейти по списку.
  • Если элемент больше largest, присвойте ему largest.
  • Если элемент больше second_largest, но меньше largest, присвойте ему значение 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

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

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

Давайте установим 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) кажется правильным. Второе по величине значение совершенно неверно. Что происходит?

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

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

А как же second_largest?

Когда мы присваиваем новое значение 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)

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

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

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

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

Давайте снова пройдемся по нашей логике.

• largest установлен на -3
• second_largest установлено на -2

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

• largest установлен в -1; second_largest устанавливается на старое значение largest, которое равно -3

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

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 прогонов).

Answer 3

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

Answer 4

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

Answer 5

«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 уникальных значений в списке.

Answer 6

Скопируйте List в List_copy. Получить наибольшее значение и получить его позицию по:

Highest_value = max(List_copy)
Highest_position = List_copy.index(max(List_copy))

Назначить 0 на Highest_value.

List_copy[Highest_position] = 0

И снова запусти свою линию.

Second_Highest = max(List_copy)

Answer 7

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

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)

Answer 8

Сортировка списка, и если список не нулевой, извлеките последние два элемента

>>> a=[0,6,8,5,10,5]
>>> a.sort()
>>> a
[0, 5, 5, 6, 8, 10]
>>> if a:
...  print a[-1],a[-2]
... 
10 8

Простой и самый эффективный:)

Теперь, если сортировка не требуется, найдите max, удалите max, найдите max снова

>>> a=[0,6,8,5,10,5]
>>> max(a)
10
>>> a.remove(max(a))
>>> max(a)
8
>>> 

Конечно, вы потеряете исходный список, но вы также можете создать временный список.

Answer 9

Другое решение, которое использует только базовые функции Python, можно увидеть ниже:

>>> largest = max(lst)
>>> maxIndex = lst.index(largest)
>>> secondLargest = max(max(lst[:maxIndex]), max(lst[maxIndex+1:]))

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

Тривиально показать, что это O (n) время и O (1) пространство. Мы просматриваем список один раз, чтобы найти самый большой элемент, затем снова, чтобы найти второй по величине. Мы храним только самые большие значения и индекс наибольшего значения.

Answer 10

Я знаю, что эта тема старая, но здесь есть простое решение этой проблемы. Проверено на heapq.nlargest, и это немного быстрее (сортировка не требуется):

Работает как для положительных, так и для отрицательных чисел.

Функция ниже: максимальное использованное время: 0,12, максимальное использованное количество памяти: 29290496 heapq.nlargest: максимальное использованное время: 0,14, максимальное использованное количество памяти: 31088640

def two_highest_numbers(list_to_work):

    first = None
    second = None

    for number in list_to_work:
        if first is None:
            first = number
        elif number > first:
            second = first
            first = number
        else:
            if second is None:
                second = number
            elif number > second:
                second = number

return [first, second]