添加到零的组合
给定五个排序列表: List1、List2、List3、List4、List5，每个列表的长度为n。如果有5 (int)个数字(每个列表中有1个)，求和为零返回true。我的目标是确保算法是O(n)。不经意间，我可以考虑创建一个包含5个链表之和的散列映射，或者计算这5个链表的值，使得o(n*n)。我在寻找优化或降低复杂性的方法，但我被卡住了。
我的Python代码：
def getIndicesFromFiveArrays(List1,List2,List3,List4,List5,t):
a,b,c,d,e=0,0,0,0,0
while(List1[a]+List2[b]+List3[c]+List4[d]+List5[e]!=t):
b=b+1
if b==len(List2):
return (-1,-1)
if List1[a]+List2[b]+List3[c]+List4[d]+List5[e]<t:
a=a+1
b=b-1
c=c-1
d=d-1
e=e-1
if a==len(List1):
return (-1,-1)
return (a,b,c,d,e)编辑1:顺便说一下，这不是家庭作业，你可以检查我的其他问题，自己验证。谢谢..
回答 2
Stack Overflow用户
发布于 2012-07-19 14:57:15
如果有2个列表，你可以从列表1中提取一个数字，然后在列表2中查找该数字的负数。如果你用一个集合替换列表2，那么总体复杂度将为O(n)。
如果有3个列表，您将从列表1中获取一个数字，然后从列表2中获取一个数字，复杂度为O(n^2)。如果将列表3替换为一个集合，则总体复杂度将为O(n^2)。
因此，我认为5个列表/集合的总体复杂度不能低于O(n^4)。
Stack Overflow用户
发布于 2012-07-19 21:21:17
有一个O(n^3)的解决方案，灵感来自MRAB的评论。
首先，将列表1中的每个值与列表2中的每个值组合起来，并将其存储在一个集合中。调用结果集1和2，它有n^2个值。
接下来，将集合1和2与列表3组合。调用结果集1和2和3，它有n^3个值，并且需要n^3个步骤来构造。
接下来，组合列表4和5。调用结果集4和5，它有n^2个值。
最后，检查集合4和5中的值是否等于集合1和2和3中的值的倒数。此步骤需要n^2个步骤。
该方法使用O(n^3)空间和O(n^3)时间。
正如Karoly Horvath所指出的，您实际上不需要存储集合1和2和3，您可以在最后一步中从集合1和2即时构建它。此方法仅使用O(n^2)空间，但仍需要O(n^3)时间。代码如下：
l1 = [1,2,3,4,5,10]
l2 = [1,2,3,4,5,11]
l3 = [1,2,3,4,5,12]
l4 = [1,2,3,4,5,13]
l5 = [1,2,3,4,5,-46]
def test():
l1_2 = [a + b for a in l1 for b in l2]
set4_5 = set([a + b for a in l4 for b in l5])
return any([True for x in l1_2 for y in l3 if -(x + y) in set4_5])
print test()https://stackoverflow.com/questions/11562888
复制
腾讯云开发者
