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

Question

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

6

我需要使用递归方式在Python列表中返回第二小的数字，不能使用循环。我的做法是创建一个帮助函数，返回列表中最小和第二小的值的元组，然后在我的second_smallest函数中只取tuple[1]。

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()。如何修复这个问题以处理嵌套列表？

- VD18421

你错误的明显来源是你没有完成整合那段代码。如果L[0]是一个列表，那么你必须对它进行递归，然后继续处理L[1]。你不能再使用L[0]了，因为它是一个列表，而不是一个整数。不过你走在了正确的轨道上。尝试像这样做：l0,l1 = s_smallest(L[0]); m0,m1=s_smallest(L[1:]); 然后合并 l0,l1,m0,m1。 - aghast

此外，还要注意可能性（就像你的例子中一样），即当len(L)==2时可能仍然涉及到一个或两个列表。你可能应该一直递归下去，并处理长度为1的情况下的None或其他内容。 - aghast

2个回答

0

完整解决方案

使用纯粹的functools.reduce，不需要循环，来处理任意嵌套的列表：

import functools

def helper(acc, x):
    if type(x) is list:
        return functools.reduce(lambda acc, x: helper(acc, x), x, acc)
    else:
        if x < acc[0]:
            return (x, acc[0])
        elif x < acc[1]:
            return (acc[0], x)
        else:
            return (acc[0], acc[1])

def second_smallest(l):
    if len(l) < 2:
        return None
    else:
        if l[0] <= l[1]:
            return functools.reduce(lambda acc, x: helper(acc, x), l[2:], (l[0], l[1]))
        else:
            return functools.reduce(lambda acc, x: helper(acc, x), l[2:], (l[1], l[0]))

>>> second_smallest([1,2,[0,3,[-1,-2]]])
(-2, -1)

- evocatus

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Mulan · Accepted Answer

我建议将列表展开和最小值约简分为两个单独而明确的任务

deepReduce将使用指定的约简函数来约简列表中的列表
deepMin使用min执行deepReduce

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 deepMin<b>2</b> (xs):
  # notice we change to use tuple of math.inf now
  <b>x1, x2 = </b>deepReduce (<b>min2</b>, <b>(math.inf,</b> math.inf<b>)</b>, xs)
  return <b>x2</b>

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

我应该指出，我们根本不需要触及 deepReduce，这就是关键 - 我们应该能够对嵌套列表进行任何任意的深度操作，而无需将该行为静态编码到我们的函数中。

现在，您可以编写任何想要的深度规约器，并使用 deepReduce 调用它。