python - 使用递归在Python 3中的列表列表中查找第二小的int

Question

这个问题已经有答案了:

Recursively find the kth largest int in list of list of int in Python (2 个回答)

已关闭 7 年前。

我想在可能存在空列表的列表列表中找到第二小的整数。我被困在平坦的台阶上。

我的想法

1. 未排序的列表，例如 [1, [3, 2], [[]], [4]],[[]], [12, 12], [[12], []], [ []]]

2. 卡住了!!!!!!用纯递归压平列表。我尝试在递归步骤的第一部分中执行此操作。上面的例子就变成了 [1, 3, 2, 4], [12,12,12]

3. 找到第二小的int(已完成)

这是代码

def find(abc):
#base case
if len(abc) == 2:
    if isinstance(abc[0], list) and isinstance(abc[1], list):
        re = find(abc[0] + abc[1])
    elif isinstance(abc[1], list):
        re = find(abc[:1] + abc[1])
    elif isinstance(abc[0], list):
        first = find(abc[0] + abc[1:])
    else:
        if abc[0] > abc[1]:
            re = (abc[0], abc[1])
        else:
            re = (abc[1], abc[0])
# recursive step
else:
    #i think this part has problem 
    # flatten the list
    if isinstance(abc[0], list):
        re = find(abc[0] + abc[1:])
    # if this element is interger
    else:
        current = abc[0]
        second, first = find(abc[1:])
        if (second < current):
            re = (second, first)
        elif (current > first) and (second >= current):
            re = (current, first)
        else:
            re = (first, current)            
return re
e.g   find([[[]], [12, 12], [[12], []], [[]]]) -> (12, 12)
      find([1, [2, 3], [[]], [4]]) -> (2, 1)

Answer 1

只是解决问题:您必须处理递归中空列表的情况。对您的代码进行最小(并且确实有些黑客行为)的更改将如下所示:

import sys 

def find(abc):
    #base case
    if len(abc) == 2:
        if isinstance(abc[0], list) and isinstance(abc[1], list):
            re = find(abc[0] + abc[1:])
        elif isinstance(abc[1], list):
            re = find(abc[:1] + abc[1])
        elif isinstance(abc[0], list):
            re = find(abc[0] + abc[1:])
            # ^^^ fixed typo (ifs could be simplified by dropping first if)
        else:
            if abc[0] > abc[1]:
                re = (abc[0], abc[1])
            else:
                re = (abc[1], abc[0])
    # recursive step
    else:
        # CHANGE HERE
        if len(abc) == 0:   # @HACK: handle empty list
            return (sys.maxsize, sys.maxsize)
        # CHANGE ENDS
        if isinstance(abc[0], list):
            re = find(abc[0] + abc[1:])
        # if this element is integer
        else:
            current = abc[0]
            second, first = find(abc[1:])
            if (second < current):
                re = (second, first)
            elif (current > first) and (second >= current):
                re = (current, first)
            else:
                re = (first, current)            
    return re # @TODO: possibly filter out maxsize in final result

这远非完美(例如，如果没有足够的值并且可能存在其他错误，则产生 maxsize)。

重构您的代码:因此，我会用两种方式重构你的代码。首先，我将展平和搜索分开(即先展平，然后搜索展平列表):

def flatten(li):
    for el in li:
        try:    # if strings can be in list, would have to check here
            for sub in flatten(el):
                yield sub
        except TypeError:
            yield el

def find(abc):
    abc = list(flatten(abc))

    def _smallest2(abc):
        # basically your implementation for finding the smallest two values
        if len(abc) <= 2:
            return tuple(sorted(abc, reverse=True))
        current = abc[0]
        second, first = _smallest2(abc[1:])
        if (second < current):
            re = (second, first)
        elif (current > first) and (second >= current):
            re = (current, first)
        else:
            re = (first, current)       
        return re

    return _smallest2(abc)

其次，我会使用 heapq.nsmallest而不是您的搜索实现:

import heapq

def flatten(li):
    for el in li:
        try:    # if strings can be in list, would have to check here
            for sub in flatten(el):
                yield sub
        except TypeError:
            yield el

def find(li):
    return tuple(heapq.nsmallest(2, flatten(li))[::-1])

如果您可以接受稍微不同的返回值，请随意删除元组和[::-1]。

替代实现:虽然出于各种原因(例如稳健性、表现力)，我更喜欢上面的重构代码，但这里有一个替代实现，可以说它更符合您最初的问题。此实现背后的主要思想是仅检查第一个元素是否是列表？如果是，则压平；如果不是，则递归地向下查找列表的尾部:

def find(abc):
    try:                                                          # first element is list
        return find(abc[0] + abc[1:])                             #  -> flatten
    except:                                                       # first element is value
        if len(abc) <= 1: return abc                              # -> either end recursion
        return sorted(abc[:1] + find(abc[1:]), reverse=True)[-2:] # -> or recurse over tail

请注意，返回类型略有不同(列表而不是元组)。您可以将 sorted 替换为 heapq.nsmallest(对于较小的 n 来说，这可以说更有效)。