python - 最长的算术级数
问题描述
给定一个数字列表arr (not sorted) ,在其中找到最长的算术级数。
数组:整数 a
1 ≤ arr.size() ≤ 10^3。和 -10^9 ≤ arr[i] ≤ 10^9。
例子:
arr = [7,6,1,9,7,9,5,6,1,1,4,0] --------------输出= [7,6,5, 4]
arr = [4,4,6,7,8,13,45,67] --------------输出= [4,6,8]
from itertools import combinations
def arithmeticProgression2(a):
n=len(a)
diff = ((y-x, x) for x, y in combinations(a, 2))
dic=[]
for d, n in diff:
k = []
seq=a
while n in seq:
k.append(n)
i=seq.index(n)
seq=seq[i+1:]
n += d
dic.append(k)
maxx=max([len(k) for k in dic])
for x in dic:
if len(x)==maxx:
return x
如果arr.size()足够大。我的代码将运行超过 4000 毫秒。
例子 :
arr = [randint(-10**9,10**9) for i in range(10**3)]
运行时间> 4000 毫秒
如何降低上述解决方案的空间复杂度?
解决方案
使代码变慢的原因之一是您从头开始为每一对构建系列,这不是必需的:
- 您实际上并不需要每次都构建k 。如果你只保留进度的步长、长度和开始(或结束)值,你就知道了。只为最终结果显式构建进程
- 通过对每一对执行此操作,您还创建了系列,其中起点实际上位于较长系列的中间(具有相同的步骤),因此您部分地做了双重工作,以及无用的工作,如在这种情况下,较早开始的进程显然会比当前分析的进程长。
- 它使您的代码在 O(n³) 时间内运行,而不是可能的 O(n²)。
以下似乎使用动态编程在 O(n²) 中更快地返回结果:
def longestprogression(data):
if len(data) < 3:
return data
maxlen = 0 # length of longest progression so far
endvalue = None # last value of longest progression
beststep = None # step of longest progression
# progressions ending in index i, keyed by their step size,
# with the progression length as value
dp = [{} for _ in range(len(data))]
# iterate all possible ending pairs of progressions
for j in range(1, len(arr)):
for i in range(j):
step = arr[j] - arr[i]
if step in dp[i]:
curlen = dp[i][step] + 1
else:
curlen = 2
dp[j][step] = curlen
if curlen > maxlen:
maxlen = curlen
endvalue = arr[j]
beststep = step
# rebuild the longest progression from the values we maintained
return list(reversed(range(endvalue, endvalue - maxlen * beststep, -beststep)))
推荐阅读
- cmd - 考虑到无法删除通话记录,如何删除不和谐的PM?
- docker - 如何在openshift中部署apache服务器?
- javascript - 我如何在反应中从 Json 对象中读取单个元素?
- ansible - 如何正确管理 ansible 变量和 group_vars?
- mysql - 如何明智地获得第二高薪部门?
- javascript - 什么是纱线中的“提升清单”
- java - 如何使用 Selenium 和 Java 为整数值调用 sendKeys() 方法
- sql - SQL:名为 IN 的列导致查询错误
- php - 调用未定义的函数 GuzzleHttp\Handler\curl_reset()
- java - 我们如何以编程方式添加公式选项卡以及使用 java rest api 客户端在 docusign 中添加规则?