时间戳

首页 > 解决方案 > 递归查找最小值（无内置或循环）

python - 递归查找最小值（无内置或循环）

问题描述

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

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:])

提前致谢！

标签： pythonpython-3.xlistrecursion

解决方案

如果您仅限于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

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

推荐阅读