recursion - 将递归转化为分而治之
问题描述
我正在尝试返回列表中最小的三个项目。以下是我编写的 O(n) 解决方案:
def three_smallest(L):
# base case
if (len(L) == 3):
return sorted(L)
current = L[0]
(first_smallest,second_smallest,third_smallest) = three_smallest(L[1:])
if (current < first_smallest):
return (current, first_smallest, second_smallest)
elif (current < second_smallest):
return (first_smallest, current, second_smallest)
elif (current < third_smallest):
return (first_smallest, second_smallest, current)
else:
return (first_smallest,second_smallest,third_smallest)
现在我正在尝试编写一种分而治之的方法,但我不确定应该如何划分列表。任何帮助,将不胜感激。
请注意,这个解决方案(据我所知)不是分而治之。它只是一个基本的递归解决方案,因为分而治之涉及将长度为 n 的列表除以整数 b,并在这些部分上调用算法。
解决方案
对于分而治之,您通常希望将一组(大致)分成两半,而不是一个一个地削减它。也许以下内容可以满足您的需求?
def three_smallest(L):
if (len(L) <= 3): # base case, technically up to 3 (can be fewer)
return sorted(L)
mid = len(L) // 2 # find the midpoint of L
# find (up to) the 3 smallest in first half, ditto for the second half, pool
# them to a list with no more than 6 items, sort, and return the 3 smallest
return sorted(three_smallest(L[:mid]) + three_smallest(L[mid:]))[:3]
请注意,由于基本情况的不等式,此实现没有最小列表大小要求。
在规模的另一端,您的原始实现仅限于具有少于一千个值的列表,否则它将破坏递归堆栈。上面给出的实现能够毫无问题地处理一百万个值的列表。
推荐阅读
- apache-kafka - Kafka Streams v0.10 是否支持多分区消费数据?
- python - 根据列值将 pandas DF 拆分为相等的块
- javascript - Excluding accents from the vue filter, using bootstrap-vue table filter feature
- php - Laravel 错误:查询未从 MySQL 数据库返回某些列
- flutter - 什么是线性布局与 gridlayoutmanager (android) 在颤振中的等价物?
- python - 如何在烧瓶项目中编辑存储在数据集中的文件
- angular - Angular 多页数据保留挑战
- python - 如何将预测应用于 xgboost 交叉验证
- html - 多种形式只需单击一个按钮 puppeteer
- c# - 如何使用 Vector3.MoveTowards Unity 制作对象曲线?