使用递归返回嵌套列表中的第二个最小数字

Question

我必须使用递归返回python列表中的第二个最小数字,并且没有循环.我所做的是创建一个辅助函数,它返回列表中(最小,第二小)值的元组,然后我只需要使用tuple[1]我的second_smallest函数.

def s_smallest(L):

    if(len(L) == 2):
        if (L[0] >= L[1]):
            return (L[1],L[0])
        else:
            return (L[0],L[1])
    else:
        first_smallest,second_smallest = s_smallest(L[1:])

        if L[0] >= first_smallest and L[0] <= second_smallest:
            return (first_smallest, L[0])

        elif L[0] <= first_smallest:
            return (L[0], first_smallest)

        else:
            return (first_smallest, second_smallest)

这有效,但现在我需要处理嵌套列表,所以s_smallest([1,2,[3,0]])应该返回(0,1).我试过这样做:

if isinstance(L[0],list):
    first_smallest,second_smallest = s_smallest(L[0])
else:
    first_smallest,second_smallest = s_smallest(L[1:])

如果它是一个列表,获取第一个最小和第二个最小值,但我得到一个错误说builtins.TypeError: unorderable types: int() >= list().如何解决此问题以处理嵌套列表？

Answer 1

我可能会建议将不需要的列表和最小的减少分成两个单独的,定义明确的任务

• deepReduce 将使用指定的reduce函数减少列表列表
• deepMin执行deepReduce使用min

import math # used for math.inf

def min (x,y):
  return x if x < y else y

def deepReduce (f, y, xs):
  if not xs:
    return y
  elif isinstance(xs[0], list):
    return deepReduce(f, deepReduce(f, y, xs[0]), xs[1:])
  else:
    return deepReduce(f, f(y, xs[0]), xs[1:])

def deepMin (xs):
  return deepReduce (min, math.inf, xs)


data = [1,2,[7,[6,1,3,[0,4,3]],3,4],2,1]
print(deepMin(data))
# 0

哦,但你说你想要第二小的数字.让我们重新编写一下代码.当然我一直都知道,但两次回答这个问题可以让我展示这个具体实现的多功能性 - 粗体的变化

def min2 (xs, y):
  # x1 is the smallest, x2 is second smallest
  x1, x2 = xs
  if (y < x1) and (y < x2):
    return (y, x2)
  elif y < x2:
    return (x1, y)
  else:
    return (x1, x2)

def deepMin2 (xs):
  # notice we change to use tuple of math.inf now
  x1, x2 = deepReduce (min2, (math.inf, math.inf), xs)
  return x2

data = [1,2,[7,[6,1,3,[0,4,3]],3,4],2,1]
print(deepMin2(data))
# 1

我应该指出,我们根本不需要触摸deepReduce,这就是重点 - 我们应该能够在嵌套列表上执行任意深度操作,而不必将该行为静态编码到我们的函数中.

现在你可以编写你想要的任何深度减速器并调用它 deepReduce