使用递归查找列表中的第二个最小数字

Question

我知道有关于这个主题的问题,但没有一个答案对我有帮助.我不需要实现代码的帮助,我只需要帮助整理递归过程.

我最初想的是递归地返回每个级别的元组并进行比较以找到第二个最小值.但这不起作用,因为我希望我的函数最终只返回1个值 - 第二个最小值.

我将如何处理此问题的递归过程？谢谢!

编辑:抱歉没有包含足够的详细信息,所以这里有.

功能应如下工作:

>>> sm([1,3,2,1,3,2])
>>> 2

第二次编辑: 抱歉延迟,我一直忙到现在,终于能够坐下来把我的想法放到代码中了.它按预期工作,但老实说,我认为这是一种非常糟糕和低效的递归方式,因为你可能会说我是这个概念的新手.

使用下面的伪代码重新解释我的原始问题:是否有可能做我在这里做的,但没有将它包装在第二个函数中？也就是说,是否有可能只有递归调用自身的函数,并返回1个数字 - 第二个最小的数字？

def second_smallest(list):
    def sm(list):
        if base case(len of list == 2):
            return ordered list [2nd smallest, smallest]
        else:
            *recursive call here*
            compare list[0] with returned ordered list
            eg: [3, [5,2]]
            re-arrange, and return a new ordered list
            [3,2]
    return sm(list)[0]

Answer 1

您可以编写递归函数来接受 3 个参数：迄今为止遇到的第一个和第二个最小值，以及列表的其余部分（您尚未检查）。

然后，通过将列表参数的第一个元素与迄今为止最小的两个元素进行比较，您可以选择 3 个中的哪 2 个作为参数传递到下一个递归。

您需要将此递归函数包装在一个表示函数中，该函数设置并调用递归函数，同时处理元素少于 2 个列表等情况。

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)

请注意，此函数做了一些多余的工作，因为它无法知道它是否首先被调用，或者是否递归地调用自身。另外，+创建一个新列表，因此对于大小为 n 的列表，此代码可能需要 O(n^2) 时间。