使用遞歸在列表中找到第二小的數字

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個元素的例子。

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的列表。

Answer 2

我可以想到幾種方法。速度慢的是找到給定列表的最大值，然後重複列表的其餘部分。列表長度爲2時，不要進行遞歸調用。

更快的是找到最小的元素，在列表的其餘部分重複，只迭代兩次。編寫一個例程，以這種方式查找最小的元素，然後將其包裝在一個調用n = 2的例程中。

這足夠了嗎？

Answer 3

一種可能的方法是創建一個取3個參數的函數：list和可選的smallest_value和second_smallest。在函數pop中，第一個元素將其與最小值和次小值進行比較，並根據需要更改值。然後再次使用新的list，smallest和second_smallest調用該函數。當列表爲空時遞歸應該終止，並返回第二小。

有一些棘手的狀態（當一個/兩個值尚未設置）。但我認爲這是實現細節，您可以再次詢問您是否有任何編碼問題。

Answer 4

你可以使用經典的分而治之。假設f(x)是返回包含列表x中的最小和次最小元素的元組(a,b)的函數。

基本情況是當x有0或1個元素。超過基部的情況下，分裂列表2，復發找到每個半的至少兩種元素，然後挑選這些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爲「無窮大「。

Answer 5

您可以使用標誌來跟蹤您是否處於呼叫的最外層。

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 

Answer 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程序文件運行此代碼的工作

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