Python在嵌套列表递归中获得第二小的价值 [英] Python Get Second Smallest Value in Nested Lists Recurssion

问题描述

second_smallest(input_list)函数必须从嵌套列表的列表中返回第二个最小值.函数不得再通过一次列表(不能展平然后继续)，必须使用默认的内置python函数(不导入)，必须使用递归和没有失败.传递给函数的列表可以是以下形式:

The second_smallest(input_list) function has to return the second smallest value from a list of nested lists. The function MUST NOT pass through the list more then once (can't flatten and then proceed), must use default built-in python functions (no import), must use recursion and NO LOOPS. The list passed into the function can be the form of:

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

所以input_list可以是所有这些形式，并且所有这些形式的返回都应该为2

So the input_list can be of all these forms and the return of all of these should be 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

，但是此代码仅适用于未嵌套的列表.那么如何解决我的实现(或完全更改)以解决此问题?

but this code only works for lists that are not nested. So how can I adjust my implementation (or change completely) in order to solve this problem?

我想办法检查当前块的递归深度，有没有办法做到这一点?

A way I though of is checking how deep in recursion the current block is in, is there a way to do that?

推荐答案

如果禁止循环，我们可以二等分:

Ok if loops are forbidden we can bisect:

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]

这篇关于Python在嵌套列表递归中获得第二小的价值的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！