我想在可能存在空列表的列表列表中找到第二小的整数。我被困在平坦的台阶上。
我的想法
未排序的列表,例如 [1, [3, 2], [[]], [4]],[[]], [12, 12], [[12], []], [ []]]
卡住了!!!!!!用纯递归压平列表。我尝试在递归步骤的第一部分中执行此操作。上面的例子就变成了 [1, 3, 2, 4], [12,12,12]
找到第二小的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)
最佳答案
只是解决问题: 您必须处理递归中空列表的情况。对您的代码进行最小(并且确实有些黑客行为)的更改将如下所示:
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
来说,这可以说更有效)。
关于python - 使用递归在Python 3中的列表列表中查找第二小的int,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/35595116/