我想知道,给一个整数列表,比如说l,如果我们被允许从该列表中选择3点的整数,也就是说left,middle,right,其中middle > left, right并left, middle, right出现在列表中的顺序(即index(left)<index(middle)<index(right)),确实存在一个O(n)寻找解决方案最大的middle - left + middle - right？您可能会认为不符合这些条件的列表不会出现(例如[5,0,5],如Eric Duminil所指出的那样)
目前,我能够提出我认为(大致)一个O(n^2)解决方案(如果我错了,请纠正我).
从本质上讲,我目前的想法是:
maximum = 0
for idx in range(1, N - 1):
left = min(l[0: idx])
right = min(l[idx + 1:])
middle = l[idx]
if left < middle and right < middle:
new_max = middle - left + middle - right
maximum = max(new_max, maximum)
帮助/提示将不胜感激.
谢谢!
所以最近我遇到了这个编程问题,我似乎无法使复杂性降低(我当前的代码运行在O(n ^ 2)).
基本上,我有四个不同的列表(我使用python btw)的整数,正面和负面,比如列表A,B,C,D.现在,这些列表中的每一个都有1000个整数,这些整数的范围是-25000到25000包括在内.现在,假设从每个列表中我们选择一个整数,比如a,b,c,d.我想找到这些a,b,c,d的最快方法是a + b = - (c + d).
目前,我的方法依赖于遍历a,b和c,d的每个可能组合,然后尝试查找集合中的元素(a + b)是否存在于集合中 - (c + d).当然,这是不切实际的,因为它在O(n ^ 2)时间内运行,考虑到大的列表大小(1000),更是如此.
因此,我想知道是否有人能想到更有效的方式(最好是O(n log n)或更小),如果可能的话用python编码.
如果它相当令人困惑,请道歉.如果您有任何疑问请通知我,我会尽量提供更多说明.
编辑:
这个问题是一个更大问题的一部分.更大的问题表明,如果我们有4个数字序列,每个数字最多1000个整数,比如A,B,C,D,找到a,b,c,d使得a + b + c + d = 0.
我问了上面的问题,因为a + b + c + d = 0意味着a + b = - (c + d),我认为这将导致解决问题的最快方法.如果有人能想到更快的方式,请与我分享.
提前致谢!:)