python - 递归查找最小值(无内置或循环)

Question

下面是我在嵌套列表中查找最小整数的代码。它抛出此错误:

TypeError: '<' not supported between instances of 'int' and 'list'

我知道原因，但不知道如何解决。除了 len、int、str 和append 之外，我无法使用循环或内置函数。

def min(nest):
    compareNum = nest[0]

    if len(nest) == 1:         
        return nest[0]      

    if compareNum < min(nest[1:]):         
       return compareNum     

    else:         
        return min(nest[1:])  

提前致谢!

Answer 1

如果您仅限于 len、int、str 和 append，则如下所示为我工作。它甚至可以处理空列表。

def is_a_list(input):
    return str(input)[0] == '['

def nested_min(input):
    # if type(input) is list:
    if is_a_list(input):
        length = len(input)
        if length == 0:
            return None
        if length == 1:
            return nested_min(input[0])
        else:
            mid = length // 2
            first = nested_min(input[:mid])
            second = nested_min(input[mid:])
            if first is None:
                return second
            elif second is None:
                return first
            return first if first < second else second
    else:
        return input

如果允许使用 type()，请使用注释行而不是使用 is_a_list() 的未注释版本，并删除该辅助函数。

我不太喜欢逐一削减递归调用。相反，该解决方案在每次迭代时将列表和子列表分成两半，因此它应该能够处理非常大的输入。考虑以下测试用例:

from random import randint

rnd_list = [randint(10, 1000000) for _ in range(100000)]
# use builtin min to confirm answer
print("rnd_list minimum is " + str(min(rnd_list)))          
test_list = [42, 17, [99, 100], [rnd_list], [], 10000]
print("nested minimum is " + str(nested_min(test_list)))

这会产生如下输出:

rnd_list minimum is 22
nested minimum is 17

或

rnd_list minimum is 12
nested minimum is 12

但与其他建议的解决方案一起使用时超出了最大递归深度。