Как найти второй минимум питон

I’d like to add another, more general approach:
Here’s a recursive way of finding the i-th minimums of a given list of numbers

def find_i_minimums(numbers,i):
    minimum = float('inf')
    if i==0:
        return []
    less_than_i_minimums = find_i_minimums(numbers,i-1)
    for element in numbers:
        if element not in less_than_i_minimums and element < minimum:
            minimum = element
    return less_than_i_minimums + [minimum]

For example,

>>> find_i_minimums([0,7,4,5,21,2,6,1],3) # finding 3 minimial values for the given list
[0, 1, 2]

( And if you want only the i-th minimum number you’d extract the final value of the list )

The time-complexity of the above algorithm is bad though, it is O(N*i^2) ( Since the recursion depth is i , and at each recursive call we go over all values in ‘numbers’ list whose length is N and we check if the minimum element we’re searching for isn’t in a list of length i-1, thus the total complexity can be described by a geometric sum that will give the above mentioned complexity ).

Here’s a similar but alternative-implementation whose time-complexity is O(N*i) on average. It uses python’s built-in ‘set’ data-structure:

def find_i_minimums(numbers,i):
    minimum = float('inf')
    if i==0:
        return set()
    less_than_i_minimums = find_i_minimums(numbers,i-1)
    for element in numbers:
        if element not in less_than_i_minimums and element < minimum:
            minimum = element
    return less_than_i_minimums.union(set({minimum}))

If your ‘i’ is small, you can use the implementations above and then extract how many minimums you want ( or if you want the second minimum, then in your case run the code for i=2 and just extract the last element from the output data-structure ).
But if ‘i’ is for example greater than log(N) , I’d recommend sorting the list of numbers itself ( for example, using mergesort whose complexity is O(N*log(N)) at worst case ) and then taking the i-th element. Why so? because as stated, the run-time of the algorithm above is not great for larger values of ‘i’.

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

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

Входные данные

На вход подаётся последовательность целых неотрицательных чисел, заканчивающаяся нулём. Все числа в последовательности неотрицательные, по значению не превосходящие 109.

Выходные данные

Выведите ответ на задачу.

Примеры
Ввод
1
7
9
0
3
2
2
1
1
0
Вывод
7
1

Вот мой код:

1
2
3
4
5
6
7
8
9

min 1 = 10**9
min 2 = 10**9
elem = int(input())
while elem!=0:
     if elem < min 1:
         min 2 = min 1
         min 1 = elem
     elem = int(input())
print(min 2)

Функция действительно может быть изменена, чтобы найти вторую наименьшую:

def second_smallest(numbers):
    m1, m2 = float('inf'), float('inf')
    for x in numbers:
        if x <= m1:
            m1, m2 = x, m1
        elif x < m2:
            m2 = x
    return m2

Старая версия основывалась на деталях реализации Python 2, которые None всегда сортируются перед чем-либо еще (поэтому он тестируется как “меньше” ); Я заменил это с помощью float('inf') как дозорного, так как бесконечность всегда проверяется как больше любого другого числа. В идеале исходная функция должна была использовать float('-inf') вместо None там, чтобы не привязываться к деталям реализации, другие реализации Python могут не делиться.

Демо:

>>> def second_smallest(numbers):
...     m1, m2 = float('inf'), float('inf')
...     for x in numbers:
...         if x <= m1:
...             m1, m2 = x, m1
...         elif x < m2:
...             m2 = x
...     return m2
... 
>>> print second_smallest([1, 2, 3, 4])
2

Вне функции, которую вы обнаружили, почти так же эффективно использовать функцию heapq.nsmallest(), чтобы вернуть два наименьших значения из iterable, и из этих двух выбрать второе (или последнее) значение:

from heapq import nsmallest

def second_smallest(numbers):
    return nsmallest(2, numbers)[-1]

Как и вышеприведенная реализация, это решение O (N); сохраняя вариант кучи, каждый шаг принимает время logK, но K является константой здесь (2)! Что бы вы ни делали, не используйте сортировку; который принимает время O (NlogN).