使用递归返回嵌套列表中的第二个最小数字 [英] Return second smallest number in a nested list using recursion

问题描述

我必须使用递归和无循环在python列表中返回倒数第二个的数字.我所做的是创建一个帮助器函数，该函数返回列表中(最小，第二个最小)值的元组，然后我将tuple[1]放入我的second_smallest函数中.

I have to return the second smallest number in a python list using recursion, and no loops. What I have done is created a helper function that returns a tuple of the (smallest, second smallest) values in the list, and then I just take the tuple[1] in my second_smallest func.

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).我尝试这样做:

This works, but now I need to handle nested lists, so s_smallest([1,2,[3,0]]) should return (0,1). I tried doing this:

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().如何解决此问题以处理嵌套列表?

to get the first smallest and second smallest values if it is a list, but I get an error saying builtins.TypeError: unorderable types: int() >= list(). How can I fix this problem to deal with nested lists?

推荐答案

我建议将列表嵌套和最小化分成两个单独的，定义明确的任务

I might suggest separating the list unnesting and the min reducing into two separate, well-defined tasks

• deepReduce将使用指定的归约函数归约列表
• deepMin使用min
执行deepReduce

• deepReduce will reduce a list of lists using the specified reducing function
• deepMin performs a deepReduce using 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

哦，但是您说您想要 second 最小的数字.让我们稍微修改一下代码.当然，我一直都知道，但是两次回答这个问题使我能够证明这种特定实现的多功能性-粗体

Oh, but you said you want the second smallest number. Let's rework that code a little bit. Of course I knew that all along, but answering this question twice allows me to demonstrate the versatility of this specific implementation – Changes in bold

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，这就是重点–我们应该能够在嵌套列表上执行任意深度操作，而不必将该行为静态编码为函数

I should point out that we didn't have to touch deepReduce at all, which is the point – we should be able to do any arbitrary deep operation on our nested list without having to statically code that behaviour into our function.

现在，您可以编写所需的任何深度缩减器，并使用deepReduce

Now you can write whatever deep reducer you want and call it with deepReduce

这篇关于使用递归返回嵌套列表中的第二个最小数字的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！