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

Ответ 1

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

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

Вам нужно обернуть эту рекурсивную функцию в функцию представления, которая устанавливает и вызывает рекурсивную, обрабатывая такие случаи, как списки с менее чем двумя элементами.

def recurse(min1, min2, list):
    if len(list)==0:
        return min2
    first, rest = list[0], list[1:]
    if first < min1:
        return recurse(first, min1, rest)
    if first < min2:
        return recurse(min1, first, rest)
    return recurse(min1, min2, rest)

def second_smallest(list):
    if len(list) < 2:
        raise ValueError("too few elements to find second_smallest")
    a, b, rest = list[0], list[1], list[2:]
    if b < a:
        return recurse(b, a, rest)
    else:
        return recurse(a, b, rest)

Такое решение не является особенно Pythonic - это скорее функциональный стиль программирования.

Наконец, вы можете передать аргументы в начале списка и объединить две функции, чтобы получить то решение, которое вы ищете:

def second_smallest(list):
    if len(list) < 2:
        raise ValueError("too few elements to find second_smallest")
    a, b = list[0], list[1]
    a, b = min(a,b), max(a,b)
    if len(list) == 2:
        return b
    c, rest = list[2], list[3:]
    if c < a:
        return second_smallest([c,a]+rest)
    if c < b:
        return second_smallest([a,c]+rest)
    return second_smallest([a,b]+rest)

Обратите внимание, что эта функция выполняет некоторую избыточную работу, поскольку она не может знать, вызвана ли она первой, или если она вызывает рекурсивно. Кроме того, + создает новый список, поэтому этот код, скорее всего, займет время O (n ^ 2) для списка размером n.

Ответ 2

Вы можете использовать классический разрыв и побеждать. Пусть f(x) - функция, возвращающая кортеж (a,b), содержащий наименьший и следующий наименьший элементы в списке x.

Базовые случаи: когда x имеет 0 или 1 элемент. За базовым случаем разделите список на 2, повторите поиск, чтобы найти наименьшие два элемента каждой половины, затем выберите в качестве результата минимум 2 из этих 4:

def min2(x):
  if len(x) == 0: return sys.maxsize, sys.maxsize
  if len(x) == 1: return x[0], sys.maxsize
  m = int(len(x)/2)
  a1, b1 = min2(x[:m])
  a2, b2 = min2(x[m:])
  return (a1, min(b1, a2, b2)) if a1 < a2 else (a2, min(b2, a1, b1))

def secondSmallest(x)
  return min2(x)[1]

Здесь я использую sys.maxsize как "бесконечность".

Ответ 3

Вы можете использовать флаг для отслеживания того, находитесь ли вы на самом внешнем уровне вызовов.

def second_smallest(numbers, top_level=True):
    # Do your stuff and call `second_smallest(numbers[1:], False)` for any recursions.
    # When it comes to returning a value from the function, use the following.

    if top_level:
        return result[0]   # what your function ultimately returns
    return result          # [second, first] since you're still in recursive calls

Ответ 4

Я могу думать о нескольких путях. Медленным является поиск наибольшего значения данного списка, а затем повторение оставшейся части списка. Если длина списка равна 2, не выполняйте рекурсивный вызов.

Быстрее - найти наименьший элемент, вернуться в оставшуюся часть списка, итерации только дважды. Напишите процедуру, чтобы найти этот n th самый маленький элемент таким образом, а затем заверните его в подпрограмму, которая вызывает его с n = 2.

Достаточно ли такого запуска?

Ответ 5

Один из возможных способов - создать функцию с тремя параметрами: list и необязательными smallest_value и second_smallest. В функции pop первый элемент сравнивает ее с наименьшим и вторым наименьшим значением и при необходимости меняет значения. Затем снова вызовите функцию с новыми list, smallest и second_smallest. Рекурсия должна заканчиваться, когда список пуст и возвращает вторую наименьшую.

Есть несколько сложных состояний (когда один/оба значения еще не установлены). Но я думаю, что детали реализации, и вы можете снова спросить, есть ли у вас какие-либо проблемы с его кодированием.

Ответ 6

Что я понимаю из вопроса: - 1. Решение должно быть рекурсивным 2. Отсутствие внутренней функции взлома 3. Он должен вернуть второй наименьший и принять список в качестве параметра Мой код для решения этой проблемы -

from inspect import getouterframes, currentframe
def second_smallest(ls):
    level = len(getouterframes(currentframe(1)))

    if len(ls)<2:
        return None
    if len(ls) == 2:
                if level == 1:
                    return max(ls)
                else:
                    return min(ls), max(ls)
    else:
        m,n = second_smallest(ls[1:])
        if ls[0]<=m:
            n = m
            m = ls[0]
        elif ls[0] < n:
            n = ls[0]
        if level == 1:
            return n
        return m,n

Примечание. Этот код работает, если вы запустите файл программы python

Ответ 7

Вы можете сделать что-то в этом направлении:

def rmin(li, n=2):
    def _rmin(li):
        if len(li) == 1:
            return li[0]
        else:
            m = _rmin(li[1:])
            return m if m < li[0] else li[0]  

    a=[]        
    for i in range(n):
        x=_rmin([e for e in set(li) if e not in a]) 
        a.append(x)
    return x