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

Question

我知道这个主题已经有人提出了问题，但是没有一个答案能帮到我。我不需要帮忙实现代码，我只需要帮忙理清这个递归过程。

我最初想的是每个级别递归返回一个元组并比较以找到第二小的值。但这行不通，因为我希望我的函数最终只返回一个值——第二小的值。

我该如何处理这个问题的递归过程呢？谢谢！

编辑：很抱歉没有包含足够的细节，下面是更多说明。

函数应按以下方式工作：

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

第二次编辑: 抱歉耽搁了，一直很忙，现在终于能坐下来将我想到的东西编成代码了。它按照我的意愿工作，但老实说，我认为这是一种非常糟糕和低效的递归方式，正如你可能看出来的，我对这个概念还很陌生。

用下面的伪代码重新表述我的原始问题：是否可能做到像我在这里所做的那样，但不用再套一层函数呢？也就是说，是否可能有一个只递归调用自己并返回第二小的数字的函数？

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]

- Nick

---

这些数字是不同的吗？如果列表是[2,1,2,1,3,5]，那么第二小的数字是什么？ - President James K. Polk

忘了提一下，它们可以重复，所以在你给出的列表中，它将是2。而列表的最小长度也必须为2。 - Nick

展示伪代码或实际代码与第二段结合使用将会很有帮助，这样我们就知道你拥有什么。 - Michal Frystacky

你的方法是正确的，只需要在函数结束后从元组中取出一个。 - Andrey

假设规则是只能有一个调用自身的函数，那么我认为这是不可能的，因为你必须将两个信息传回给调用者：最小数和候选第二小的数。 - David van rijn

Answer 1

你可以编写递归函数，它需要三个参数：目前为止遇到的最小值和第二小的值以及你尚未检查的列表。

接着，通过比较列表参数的第一个元素与两个最小值之间的大小，你可以选择将其中两个作为下一次递归的参数。

你需要在一个展示函数中包装这个递归函数，设置并调用递归函数，同时处理那些少于 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)

这种解决方案不是特别符合 Python 的编程风格，更像是一种函数式编程的风格。

最后，你可以将参数放在列表前面，并结合这两个函数来获得你想要的解决方案：

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)的时间。

- comingstorm

Answer 2

你可以使用经典的分治法。让f(x)成为一个返回元组(a,b)，其中包含列表x中最小和次小的元素的函数。

当x有0或1个元素时，这是基本情况。超出基本情况后，将列表分成两半，递归查找每半部分的最小的两个元素，然后从这4个元素中选择最小的2个作为结果。

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作为“无穷大”。

- Gene

Answer 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

- Reti43

Answer 4

我理解的问题是： 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程序文件运行，则此代码有效。

- AlokThakur

Answer 5

我可以想到几种方法。其中一种较慢的方法是找到给定列表中的最大值，然后对剩余的列表进行递归。当列表长度为2时，不要进行递归调用。

较快的方法是找到最小元素，在列表的其余部分上进行递归，仅迭代两次。编写一个程序以此方式找到第n个最小元素，然后将其包装在一个调用n=2的例程中。

这样的开端足够了吗？

- Prune

Answer 6

一种可能的方法是创建一个带有3个参数的函数：list，可选的smallest_value和second_smallest。在函数pop中，将第一个元素与最小值和次小值进行比较，并在必要时更改这些值。然后使用新的list，smallest和second_smallest再次调用该函数。递归应在列表为空时终止并返回第二个最小值。

存在一些棘手的状态（当一个/两个值尚未设置时）。但我认为这是实现细节，如果你在编码过程中遇到任何问题，可以再次提问。

- MSeifert

Answer 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

- dawg