Вернуть 2-й самый маленький элемент в списке, используя только рекурсию

Question

У меня проблемы с этим более сложным сценарием.

Я понимаю это:

def max(alist):
    if len(alist) == 1:
        return alist[0]
    else:
        m = max(alist[1:])
        return m if m > alist[0] else alist[0]

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

Answer 1

Я бы отсортировал ( сортировка слиянием ), затем взял бы второй элемент, давая сложность времени O(nlog(n)):

def second_max(lst):
    #takes two sorted lists and merges them together
    def merge(a,b):
        if len(a) == 0: return b
        if a[0] < b[0]:
            return [a[0]] + merge(a[1:],b)
        else:
            return [b[0]] + merge(b[1:],a)
    #breaks list down and then merges back up - sorting
    def merge_sort(lst):
        if len(lst) == 1: return lst
        h = int(len(lst)/2)
        return merge(merge_sort(lst[:h]), merge_sort(lst[h:]))
    #return second element from sorted list
    return merge_sort(lst)[1]

и тест:

>>> second_max([9, 3, 9, 6, 2, 4])
3