使用递归查找列表中第二小的数字 [英] Find the second smallest number in a list using recursion

问题描述

我知道有关此主题的问题，但没有一个答案对我有帮助。我不需要实现代码的帮助，我只需要在递归过程中进行排序即可。

我本来是想在每个级别上递归返回一个元组并进行比较查找第二个最小值。但这不起作用，因为我希望函数最后只返回1个值-第二个最小值。

对于该问题，我将如何进行递归处理？谢谢！

编辑：很抱歉没有包含足够的详细信息，所以就去了。

功能应该可以如下：

 >> sm（[1,3,2,1,3,2]）
> 2 
  

第二次编辑：
抱歉，我直到现在一直很忙，终于能够坐下来并将我的想法记入代码中。它可以按预期工作，但是老实说，这是一种非常卑鄙且效率低下的递归方式，因为您可能会告诉我，这个概念是陌生的。

我的原始问题使用下面的伪代码：是否可以执行我在这里所做的操作，而无需将其包装在第二个函数中？也就是说，是否有可能仅递归地调用其自身并返回1个数字（第二个最小的数字）的函数？

  def second_smallest（list）：
 def sm（list）：
如果有基本情况（list的len == 2）：
返回有序列表[第二最小，最小] 
否则：
 *此处递归调用* 
比较列表[0]与返回的有序列表
例如：[3，[5,2]] 
重新排列，并返回a新的有序列表
 [3,2] 
 return sm（list）[0] 
  

解决方案

您可以编写递归函数以接受3个参数：到目前为止遇到的第一个和第二个最小值，以及尚未检查的其余列表

然后，通过将list参数的第一个元素与两个最小的元素进行比较，您可以选择将3个参数中的哪个作为参数传递给下一次递归。 / p>

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

  def递归（min1，min2，list）：
如果len（list）== 0：
返回min2 
首先，其余部分= list [0]，list [1：] 
，如果first< min1：
返回递归（first，min1，rest）
如果first< min2：
返回递归（min1，第一个，其余）
返回递归（min1，min2，其他）
 
 def second_smallest（list）：
如果len（list ）< 2：
引发ValueError（元素太少，无法找到second_smallest）
 a，b，rest = list [0]，list [1]，list [2：] 
如果b< a：
收益递归（b，a，其余）
其他：
收益递归（a，b，其它）
  

这种解决方案并不是特别Pythonic的，它更像是一种函数式编程风格。

最后，您可以传递列表最前面的参数，并结合使用这两个函数以获得所需的解决方案：

  def second_smallest（list）：如果len（list）<则
 2：
提高ValueError（找到第二个最小元素的元素太少）
a，b = list [0]，list [1] 
a，b = min（a，b），max（ a，b）如果len（list）== 2，则
：
返回b 
c，rest = list [2]，list [3：] 
如果c< a：
返回second_smallest（[c，a] + rest）
如果c< b：
返回second_smallest（[a，c] + rest）
返回second_smallest（[a，b] + rest）
  

请注意，此函数做了一些多余的工作，因为它不知道是先调用它还是递归调用它。另外， + 创建一个新列表，因此此代码可能需要O（n ^ 2）时间来生成大小为n的列表。

I know there has been a question asked on this topic, but none of the answers have helped me. I don't need help with implementing the code, I just need help sorting through the recursive process for this.

I was originally thinking recursively return a tuple each level and compare to find the second smallest value. But this doesn't work as I want my function to only return 1 value in the end- the 2nd smallest value.

How would I go about the recursive process for this problem? Thank you!

Edit: Sorry about not including enough details, so here goes.

Function should work as follows:

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

Second edit: Sorry for the delay, I was busy until now, finally was able to sit down and put what I had in mind into code. It works as intended, but I honestly think this is a very shitty and inefficient way of doing recursion, as you can probably tell I am new to the concept.

To rephrase my original question using the pseudo code below: Is it possible to do what I did here, but without wrapping it in a second function? That is, is it possible to have a function that only recursively calls its self, and returns 1 number- the second smallest number?

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]

解决方案

You can write your recursive function to take 3 arguments: the first and second smallest values you've encountered so far, and the rest of the list, which you haven't inspected.

Then, by comparing the first element of the list argument with the two smallest-so-far, you can choose which 2 of the 3 to pass as the arguments to the next recursion.

You need to wrap this recursive function in a presentation function, which sets up and calls the recursive one, while handling cases like lists that have less than 2 elements.

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)

This kind of solution isn't particularly Pythonic -- it's more of a functional programming style.

Finally, you can pass the arguments on the front of the list, and combine the two functions to get the kind of solution you're looking for:

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)

Note that this function does some redundant work, because it can't know if it's being called first, or if it's calling itself recursively. Also, + creates a new list, so this code will likely take O(n^2) time for a list of size n.

这篇关于使用递归查找列表中第二小的数字的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！