Python在嵌套列表递归中获得第二小值

Question

second_smallest（input_list）函数必须从嵌套列表列表中返回第二个最小值。函数不得一旦通过列表，然后必须使用默认的内置python函数（ no import ），必须使用递归和无环。列表传递到该功能的形式：

的形式

>>> [1,2,3]
>>> [[1,2],3]
>>> [[1],2,3]
>>> [[],1,2,3]
>>> [[1],[2],[3]]
>>> [1,2,3,2,[4,5],[]]

因此，input_list可以是所有这些形式的，所有这些的返回应为2

>>> [1,1,2,3]

将返回1

>>> second_smallest([[1],[2]])

有效，但是

>>> second_smallest([1])

不是

我目前拥有的是：

def second_smallest(numbers):
    '''(list of int) -> int
    This function takes in 1 parameter, input_list, and returns the second
    smallest number in the list.
    '''
    # if the length of numbers is equal to 2, then set result equal to the
    # second element if the first is less than or equal to second, otherwise
    # set result equal to the first element
    if(len(numbers) == 2):
        if(numbers[0] <= numbers[1]):
            result = numbers[1]
        else:
            result = numbers[0]
    # if the length of numbers is greater than 2, then set result equal to
    # second_smallest_help of the first to second last element in numbers if
    # first is less than or equal to last and last is greater than or equal     to
    # second, otherwise, set result equal to second_smallest of the last to the
    # second last
    else:
        if(numbers[0] <= numbers[-1] >= numbers[1]):
            result = second_smallest(numbers[:-1])
        else:
            result = second_smallest([numbers[-1]] + numbers[:-1])
    return result

但是此代码仅适用于未嵌套的列表。那么如何调整我的实现（或完全更改）以解决此问题？

我是在检查当前块中的递归中有多深，有没有办法做到这一点？

Answer 1

好的，如果禁止循环，我们可以一分为二：

def second(l):
    n = len(l)
    if n >= 2:
        f1, s1 = second(l[:n//2])
        f2, s2 = second(l[n//2:])
        if f1 is None:
            return f2, s2
        elif f2 is None:
            return f1, s1
        elif f1 < f2:
            return f1, (f2 if s1 is None or s1 > f2 else s1)
        else:
            return f2, (f1 if s2 is None or s2 > f1 else s2)
    if n == 0:
        return None, None
    elif isinstance(l[0], list):
        return second(l[0])
    else:
        return l[0], None
def master(l):
    return second(l)[1]

Answer 2

当您浏览列表中的条目时，检查它们是否为列表。如果它们是列表，则递归遍历列表。类似：

def second_smallest(input):
    two_smallest_entries = [None, None]
    def encountered(entry):
        if two_smallest_entries[0] is None or two_smallest_entries[0] >= entry:
            two_smallest_entries[1] = two_smallest_entries[0]
            two_smallest_entries[0] = entry
        elif two_smallest_entries[1] is None or two_smallest_entries[1] >= entry:
            two_smallest_entries[1] = entry
    def traverse(input):
        for entry in input:
            if type(entry) == list:
                traverse(entry)
            else:
                encountered(entry)
    traverse(input)
    return two_smallest_entries[1]
def test(correct, input):
    print second_smallest(input) == correct
test(2, [1,2,3])
test(2, [[1,2],3])
test(2, [[1],2,3])
test(2, [[],1,2,3])
test(2, [[1],[2],[3]])
test(2, [1,2,3,2,[4,5],[]])
test(1, [1,1,2,3])
test(4, [6, 4, [4, 4, 3]])