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

Question

所以我需要使用递归在整数列表中找到第二小的数字，但我无法在我的生活中设计出一种方法来做到这一点。我可以用这个找到最小的数字：

def smallest(int_list):

    if(len(int_list) == 1):
        return int_list[0]
    else:
        a = smallest(int_list[1:])
        b = int_list[0]

        if(a <= b):
            return a
        else:
            return b

谁能给我指出正确的方向？

Answer 1

这应该有效。 get_smallest_two_items() returns 具有输入的 3 个元素中最小的 2 个元素的元组。实施它应该是微不足道的。另请注意，这假定列表的最小长度为 2。

def smallest(int_list):
   smallest_two = smallest_helper(int_list)
   return smallest_two[0] if smallest_two[0]<=smallest_two[1] else smallest_two[1]

def smallest_helper(int_list):

  if(len(int_list) == 2):
    return (int_list[0],int_list[1])
  else:
    a_b = smallest(int_list[1:])
    a = a_b[0]
    b = a_b[1]
    c = int_list[0]

    return get_smallest_two_items(a,b,c)

Answer 2

比我的评论更简单的例子：

def find_nth_smallest(n, int_list):
    smallest = min(int_list)
    if n <= 1:
        return smallest
    int_list = [v for v in int_list if v != smallest]
    if int_list:
        return max(find_nth_smallest(n - 1, int_list), smallest)
    return None

示例：

Python 2.7.8 (default, Oct 20 2014, 15:05:19) 
[GCC 4.9.1] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> from kthTerm import find_nth_smallest
>>> import random
>>> random.seed()
>>> int_list = [random.randint(1, 100) for _ in range(20)]
>>> int_list
[68, 50, 6, 36, 98, 15, 81, 36, 13, 71, 76, 77, 69, 75, 79, 53, 26, 25, 18, 62]
>>> find_nth_smallest(2, int_list)
13
>>> sorted(int_list)
[6, 13, 15, 18, 25, 26, 36, 36, 50, 53, 62, 68, 69, 71, 75, 76, 77, 79, 81, 98]

Answer 3

这里：

def r_sort(a_list, ind):
    def rf(list_to_be_sorted, list_already_sorted):
        li = []
        if len(list_to_be_sorted) == 0:
            return list_already_sorted
        else:    
            x = min(list_to_be_sorted)    
            list_to_be_sorted.remove(x)
            li.append(x)
            return rf(list_to_be_sorted, list_already_sorted + li)
    return rf(a_list, [])[ind]

>>> r_sort([1,10,9,5,55,3,2], 1)  
2

Answer 4

这是一种不会破坏大型列表堆栈的方法。最好手动管理搜索端点，而不是使用引入复制的切片。

import random

def min2(xs):
    if len(xs) < 3: return xs
    n = len(xs) // 2
    return sorted(min2(xs[:n]) + [xs[n]] + min2(xs[n+1:]))[:2]

tk = range(100000)
random.shuffle(tk)
print min2(tk)

Answer 5

这里是纯递归的方式。您需要 return 元组中的第一个最小元素和第二个最小元素，依此类推。

def smallest(int_list):

    if(len(int_list) == 2):
        if (int_list[0] >= int_list[1]):
            return (int_list[0],int_list[1])
        else:
            return (int_list[1],int_list[0])
    else:
        first_smallest,second_smallest = smallest(int_list[1:])
        current_elem = int_list[0]
        if(second_smallest <= current_elem):
            return (second_smallest,current_elem)
        else:
            if (current_elem<=first_smallest):
               return (current_elem,first_smallest)
            else:
               return (first_smallest,second_smallest)



if __name__ == "__main__":    
    small = smallest([1,2,3,4])
    print small[1]
    //output 2

Answer 6

def second_smallest(my_list):

if len(my_list) == 2:
    return my_list[0] if my_list[0] > my_list[1] else my_list[1]

else:
    sec_least = second_smallest(my_list[1:])
    return sec_least if sec_least < my_list[0] else my_list[1]

Answer 7

这是一个不使用 min() 或 sorted() 的简短实现。当列表中有重复值时，它也有效。

def ss(e):
    if len(e)==2 and e[0]<=e[1]:return e[1]
    return ss(e[:-1]) if e[0]<=e[-1]>=e[1] else ss([e[-1]]+e[:-1])

print("The selected value was:", ss([5, 4, 3, 2, 1]))

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

python 3.2 - find second smallest number in a list using recursion

python

recursion

python-3.2