Как найти второй минимальный элемент массива питон

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’.

Еще одно решение с использованием — array.argpartition() из модуля Numpy (гораздо быстрее работает для больших списков):

import numpy as np

In [45]: a = np.random.randint(0, 100, size=10)

In [46]: a
Out[46]: array([ 8, 51, 63, 31, 21,  9, 28, 19, 70, 57])

In [47]: a.argpartition(2)[:2]
Out[47]: array([0, 5], dtype=int64)

дает такой же результат как и argsort()

In [48]: a.argsort()[:2]
Out[48]: array([0, 5], dtype=int64)

Сравнение производительности для массива из 1.000.000 элемтов:

In [32]: a = np.random.randint(0, 1000, size=10**6)

In [33]: lst = a.tolist()

In [34]: a.shape
Out[34]: (1000000,)

In [35]: len(lst)
Out[35]: 1000000

# Кирилл Малышев
In [51]: %timeit sorted(enumerate(lst), key=lambda x:x[1])[:2]
1.68 s ± 10.3 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

# Alban
In [49]: %timeit smallest(lst, 2)
860 ms ± 5.44 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

# jfs    
In [37]: %timeit nsmallest(2, range(len(lst)), key=lst.__getitem__)
212 ms ± 4.86 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

# avtomato    
In [38]: %timeit a.argsort()[:2]
193 ms ± 10.9 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)

# Sergey Gornostaev
In [36]: %timeit map(lst.index, nsmallest(2, lst))
75.4 ms ± 2.35 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)

# MaxU    
In [39]: %timeit a.argpartition(2)[:2]
10.8 ms ± 37.2 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

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

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).