Получите второе по величине число в списке в линейном времени

Ответ 1

Поскольку у @OscarLopez и у меня разные мнения о том, что означает второй по величине, я опубликую код в соответствии с моей интерпретацией и в соответствии с первым алгоритмом, предоставленным спрашивающим.

def second_largest(numbers):
    count = 0
    m1 = m2 = float('-inf')
    for x in numbers:
        count += 1
        if x > m2:
            if x >= m1:
                m1, m2 = x, m1            
            else:
                m2 = x
    return m2 if count >= 2 else None

(Примечание: здесь используется отрицательная бесконечность вместо None, поскольку None имеет различное поведение сортировки в Python 2 и 3 - см. Python - Найти второе наименьшее число; проверка количества элементы в numbers гарантируют, что отрицательная бесконечность не будет возвращена, когда фактический ответ не определен.)

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

Запуск тех же тестов:

second_largest([20,67,3,2.6,7,74,2.8,90.8,52.8,4,3,2,5,7])
=> 74
second_largest([1,1,1,1,1,2])
=> 1
second_largest([2,2,2,2,2,1])
=> 2
second_largest([10,7,10])
=> 10
second_largest([1,1,1,1,1,1])
=> 1
second_largest([1])
=> None
second_largest([])
=> None

Обновление

Я реструктурировал условия, чтобы радикально улучшить производительность; почти на 100% в моем тестировании на случайные числа. Причина этого заключается в том, что в исходной версии elif всегда оценивался в вероятном случае, когда следующее число не является самым большим в списке. Другими словами, практически для каждого числа в списке было сделано два сравнения, тогда как одного сравнения в основном достаточно - если число не больше второго по величине, оно также не больше самого большого.

Ответ 2

Вы можете использовать модуль heapq:

>>> el = [20,67,3,2.6,7,74,2.8,90.8,52.8,4,3,2,5,7]
>>> import heapq
>>> heapq.nlargest(2, el)
[90.8, 74]

И иди оттуда...

Ответ 3

Вы всегда можете использовать sorted

>>> sorted(numbers)[-2]
74

Ответ 4

Попробуйте решение ниже, оно O(n), и оно сохранит и вернет второе наибольшее число в переменной second. Обратите внимание, что если все элементы из numbers равны или если numbers пуст или если он содержит один элемент, переменная second будет иметь значение None - это правильно, как в тех случаев нет "второго по величине" элемента.

Остерегайтесь: это находит значение "второго максимума", если есть более одного значения, которое является "первым максимумом", все они будут рассматриваться как один и тот же максимум - в моем определении в списке, таком как: [10, 7, 10] правильный ответ 7.

def second_largest(numbers):
    first, second = None, None
    for n in numbers:
        if n > first:
            first, second = n, first
        elif first > n > second:
            second = n
    return second

Вот несколько тестов:

second_largest([20,67,3,2.6,7,74,2.8,90.8,52.8,4,3,2,5,7])
=> 74
second_largest([1,1,1,1,1,2])
=> 1
second_largest([2,2,2,2,2,1])
=> 1
second_largest([10, 7, 10])
=> 7
second_largest([1,1,1,1,1,1])
=> None
second_largest([1])
=> None
second_largest([])
=> None

Ответ 5

алгоритм быстрого выбора, кузена O (n) для быстрой сортировки, сделает то, что вы хотите. Quickselect имеет среднюю производительность O (n). Наихудшая производительность - O (n ^ 2), как и quicksort, но такая редкая, а модификации quickselect уменьшают производительность худшего случая до O (n).

Идея quickselect состоит в том, чтобы использовать ту же самую опорную точку, более низкую, более высокую идею quicksort, но затем игнорировать нижнюю часть и далее упорядочивать только более высокую часть.

Ответ 6

>>> l = [19, 1, 2, 3, 4, 20, 20]
>>> sorted(set(l))[-2]
19

Ответ 7

Зачем усложнять сценарий? Его очень простой и прямой

• Преобразование списка для установки - удаление дубликатов
• Преобразовать набор в список снова - который дает список в порядке возрастания

Вот код

mlist = [2, 3, 6, 6, 5]
mlist = list(set(mlist))
print mlist[-2]

Ответ 8

здесь есть несколько хороших ответов для типа ([]), если кто-то нуждался в одном и том же типе ({}) здесь,

def secondLargest(D):
    def second_largest(L):  
        if(len(L)<2):
            raise Exception("Second_Of_One")
        KFL=None #KeyForLargest
        KFS=None #KeyForSecondLargest
        n = 0
        for k in L:
            if(KFL == None or k>=L[KFL]):
                KFS = KFL
                KFL = n
            elif(KFS == None or k>=L[KFS]):
                KFS = n
            n+=1
        return (KFS)
    KFL=None #KeyForLargest
    KFS=None #KeyForSecondLargest
    if(len(D)<2):
        raise Exception("Second_Of_One")
    if(type(D)!=type({})):
        if(type(D)==type([])):
            return(second_largest(D))
        else:
            raise Exception("TypeError")
    else:
        for k in D:
            if(KFL == None or D[k]>=D[KFL]):
                KFS = KFL               
                KFL = k
            elif(KFS == None or D[k] >= D[KFS]):
                KFS = k
    return(KFS)

a = {'one':1 , 'two': 2 , 'thirty':30}
b = [30,1,2] 
print(a[secondLargest(a)])
print(b[secondLargest(b)])

Просто для удовольствия я попытался сделать его удобным для пользователя xD

Ответ 9

Если вы не против использования numpy (import numpy as np):

np.partition(numbers, -2)[-2]

дает вам второй по величине элемент списка с гарантированным наихудшим временем O (n).

Методы partition(a, kth) возвращают массив, в котором элемент k th тот же, что и в отсортированном массиве, все элементы до меньше, а все позади больше.

Ответ 10

Вы можете найти 2-й по величине одним из следующих способов:

Опция 1:

numbers = set(numbers)
numbers.remove(max(numbers))
max(numbers)

Вариант 2:

sorted(set(numbers))[-2]

Ответ 11

O (n): Time Сложность цикла рассматривается как O (n), если переменные цикла увеличиваются/уменьшаются на постоянную величину. Например, следующие функции имеют O (n) временную сложность.

 // Here c is a positive integer constant   
   for (int i = 1; i <= n; i += c) {  
        // some O(1) expressions
   }

Чтобы найти второе по величине число, я использовал метод ниже, чтобы сначала найти наибольшее число, а затем выполнить поиск в списке, если это там или нет.

x = [1,2,3]
A = list(map(int, x))
y = max(A)
k1 = list()
for values in range(len(A)):
if y !=A[values]:
    k.append(A[values])

z = max(k1)
print z

Ответ 12

Это можно сделать в [N + log (N) - 2] времени, что немного лучше, чем свободная верхняя граница 2N (что также можно рассматривать и для O (N)).

Хитрость заключается в использовании двоичных рекурсивных вызовов и алгоритма "теннисного турнира". Победитель (наибольшее число) появится после всех "матчей" (занимает N-1 раз), но если мы запишем "игроков" всех матчей и среди них, группируем всех игроков, которых победил победитель, второе наибольшее число будет наибольшим числом в этой группе, то есть группой "проигравших".

Размер этой группы "проигравших" - log (N), и снова мы можем отменить двоичные рекурсивные вызовы, чтобы найти самый большой среди проигравших, что займет время [log (N) - 1]. Фактически, мы можем просто линейно сканировать группу проигравших, чтобы получить ответ тоже, бюджет времени тот же.

Ниже приведен пример кода python:

def largest(L):
    global paris
    if len(L) == 1:
        return L[0]
    else:
        left = largest(L[:len(L)//2])
        right = largest(L[len(L)//2:])
        pairs.append((left, right))
        return max(left, right)

def second_largest(L):
    global pairs
    biggest = largest(L)
    second_L = [min(item) for item in pairs if biggest in item]

    return biggest, largest(second_L)  



if __name__ == "__main__":
    pairs = []
    # test array
    L = [2,-2,10,5,4,3,1,2,90,-98,53,45,23,56,432]    

    if len(L) == 0:
        first, second = None, None
    elif len(L) == 1:
        first, second = L[0], None
    else:
        first, second = second_largest(L)

    print('The largest number is: ' + str(first))
    print('The 2nd largest number is: ' + str(second))

Ответ 13

    def SecondLargest(x):
        largest = max(x[0],x[1])
        largest2 = min(x[0],x[1])
        for item in x:
            if item > largest:
               largest2 = largest
               largest = item
            elif largest2 < item and item < largest:
               largest2 = item
        return largest2
    SecondLargest([20,67,3,2.6,7,74,2.8,90.8,52.8,4,3,2,5,7])

Ответ 14

Большинство предыдущих ответов верны, но есть и другой способ!

Наша стратегия - создать цикл с двумя переменными first_highest и second_highest. Мы перебираем числа и если наше current_value больше, чем first_highest, тогда мы устанавливаем second_highest равным first_highest, а затем second_highest - текущим числом. Если наше текущее число больше, чем second_highest, тогда мы устанавливаем second_highest равным текущему номеру

#!/usr/bin/env python3
import sys
def find_second_highest(numbers):

    min_integer = -sys.maxsize -1
    first_highest= second_highest = min_integer
    for current_number in numbers:      
        if current_number > first_highest:
            second_highest = first_highest
            first_highest = current_number
        elif current_number > second_highest:
            second_highest = current_number
    return second_highest

print(find_second_highest([80,90,100]))

Ответ 15

def secondlarget(passinput):
    passinputMax = max(passinput)  #find the maximum element from the array
    newpassinput = [i for i in passinput if i != passinputMax]  #Find the second largest element in the array
    #print (newpassinput)
    if len(newpassinput) > 0:
        return max(newpassinput) #return the second largest
    return 0
if __name__ == '__main__':
    n = int(input().strip())  # lets say 5
    passinput = list(map(int, input().rstrip().split())) # 1 2 2 3 3
    result = secondlarget(passinput) #2
    print (result) #2

Ответ 16

n=input("Enter a list:")
n.sort()
l=len(n)
n.remove(n[l-1])
l=len(n)
print n[l-1]

Ответ 17

Вы также можете попробовать следующее:

>>> list=[20, 20, 19, 4, 3, 2, 1,100,200,100]
>>> sorted(set(list), key=int, reverse=True)[1]
100

Ответ 18

Цель. Чтобы найти второе по величине количество из ввода.

Вход: 5       2 3 6 6 5

Выход: 5

*n = int(raw_input())
arr = map(int, raw_input().split())
print sorted(list(set(arr)))[-2]*

Ответ 19

Простой способ:

n=int(input())
arr = set(map(int, input().split()))
arr.remove(max(arr))
print (max(arr))

Ответ 20

Чтобы сделать принятый ответ более общим, ниже приведено расширение для получения наибольшего k-го значения:

def kth_largest(numbers, k):
    largest_ladder = [float('-inf')] * k
    count = 0
    for x in numbers:
        count += 1
        ladder_pos = 1
        for v in largest_ladder:
            if x > v:
                ladder_pos += 1
            else:
                break
        if ladder_pos > 1:
            largest_ladder = largest_ladder[1:ladder_pos] + [x] + largest_ladder[ladder_pos:]
    return largest_ladder[0] if count >= k else None

Ответ 21

if __name__ == '__main__':
    n = int(input())
    arr = list(map(float, input().split()))
    high = max(arr)
    secondhigh = min(arr)
    for x in arr:
        if x < high and x > secondhigh:
            secondhigh = x
    print(secondhigh)

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

#list
numbers = [20, 67, 3 ,2.6, 7, 74, 2.8, 90.8, 52.8, 4, 3, 2, 5, 7]
#find the highest element in the list
high = max(numbers)
#find the lowest element in the list
secondhigh = min(numbers)
for x in numbers:
    '''
    find the second highest element in the list,
    it works even when there are duplicates highest element in the list.
    It runs through the entire list finding the next lowest element
    which is less then highest element but greater than lowest element in
    the list set initially. And assign that value to secondhigh variable, so 
    now this variable will have next lowest element in the list. And by end 
    of loop it will have the second highest element in the list  
    '''
    if (x<high and x>secondhigh):
        secondhigh=x
print(secondhigh)

Ответ 22

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

lis = [11,52,63,85,14]
lis.sort()
print(lis[len(lis)-2])