python 3.2 – найти второе наименьшее число в списке, используя рекурсию

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

def smallest(int_list): if(len(int_list) == 1): return int_list[0] else: a = smallest(int_list[1:]) b = int_list[0] if(a <= b): return a else: return b 

Может кто-то указать мне верное направление?

  • Почему список (my_list) изменяет объект?
  • Оптимизирует ли Python хвостовую рекурсию?
  • Как оптимально превратить многомерный список в один список элементов в Python?
  • Рекурсивный метод для балансировки скобок
  • Рекурсивная подпапка поиска и возврата файлов в списке python
  • Python IOError: Errno 13 Разрешение отклонено
  • Рекурсивный метод для балансировки скобок
  • Почему список (my_list) изменяет объект?
  • defaultdict defaultdict, вложенный
  • Как оптимально превратить многомерный список в один список элементов в Python?
  • Функция возвращает None после рекурсии
  • Оптимизирует ли Python хвостовую рекурсию?
  • 7 Solutions collect form web for “python 3.2 – найти второе наименьшее число в списке, используя рекурсию”

    Вот краткая реализация, которая не использует min() или sorted() . Он также работает, если в списке есть повторяющиеся значения.

     def ss(e): if len(e)==2 and e[0]<=e[1]:return e[1] return ss(e[:-1]) if e[0]<=e[-1]>=e[1] else ss([e[-1]]+e[:-1]) print("The selected value was:", ss([5, 4, 3, 2, 1])) 

    Вот:

     def r_sort(a_list, ind): def rf(list_to_be_sorted, list_already_sorted): li = [] if len(list_to_be_sorted) == 0: return list_already_sorted else: x = min(list_to_be_sorted) list_to_be_sorted.remove(x) li.append(x) return rf(list_to_be_sorted, list_already_sorted + li) return rf(a_list, [])[ind] >>> r_sort([1,10,9,5,55,3,2], 1) 2 

    Это должно сработать. get_smallest_two_items () возвращает кортеж с наименьшими 2 элементами из 3 введенных. Реализация его должна быть тривиальной. Также обратите внимание, что это предполагает, что минимальная длина списка равна 2.

     def smallest(int_list): smallest_two = smallest_helper(int_list) return smallest_two[0] if smallest_two[0]<=smallest_two[1] else smallest_two[1] def smallest_helper(int_list): if(len(int_list) == 2): return (int_list[0],int_list[1]) else: a_b = smallest(int_list[1:]) a = a_b[0] b = a_b[1] c = int_list[0] return get_smallest_two_items(a,b,c) 

    Простой пример, чем мой комментарий:

     def find_nth_smallest(n, int_list): smallest = min(int_list) if n <= 1: return smallest int_list = [v for v in int_list if v != smallest] if int_list: return max(find_nth_smallest(n - 1, int_list), smallest) return None 

    Пример:

     Python 2.7.8 (default, Oct 20 2014, 15:05:19) [GCC 4.9.1] on linux2 Type "help", "copyright", "credits" or "license" for more information. >>> from kthTerm import find_nth_smallest >>> import random >>> random.seed() >>> int_list = [random.randint(1, 100) for _ in range(20)] >>> int_list [68, 50, 6, 36, 98, 15, 81, 36, 13, 71, 76, 77, 69, 75, 79, 53, 26, 25, 18, 62] >>> find_nth_smallest(2, int_list) 13 >>> sorted(int_list) [6, 13, 15, 18, 25, 26, 36, 36, 50, 53, 62, 68, 69, 71, 75, 76, 77, 79, 81, 98] 

    Вот такой подход, который не взорвал бы стек для больших списков. Лучше было бы управлять конечными точками поиска вручную, а не использовать нарезку, которая вводит копирование.

     import random def min2(xs): if len(xs) < 3: return xs n = len(xs) // 2 return sorted(min2(xs[:n]) + [xs[n]] + min2(xs[n+1:]))[:2] tk = range(100000) random.shuffle(tk) print min2(tk) 

    Вот чисто рекурсивный путь. Вам нужно вернуть первый наименьший и второй наименьший элемент в кортеже и так далее.

     def smallest(int_list): if(len(int_list) == 2): if (int_list[0] >= int_list[1]): return (int_list[0],int_list[1]) else: return (int_list[1],int_list[0]) else: first_smallest,second_smallest = smallest(int_list[1:]) current_elem = int_list[0] if(second_smallest <= current_elem): return (second_smallest,current_elem) else: if (current_elem<=first_smallest): return (current_elem,first_smallest) else: return (first_smallest,second_smallest) if __name__ == "__main__": small = smallest([1,2,3,4]) print small[1] //output 2 

    def second_smallest (my_list):

     if len(my_list) == 2: return my_list[0] if my_list[0] > my_list[1] else my_list[1] else: sec_least = second_smallest(my_list[1:]) return sec_least if sec_least < my_list[0] else my_list[1] 
    Python - лучший язык программирования в мире.