2

给定五个排序列表：List1、List2、List3、List4、List5，每个列表的长度为 n。如果有 5 个 (int) 数字（每个列表中的 1 个），求和为零返回 true。我的目标是确保算法是 O(n)。在我的脑海中，我可以考虑创建一个包含 5 个链表之和的哈希映射，或者评估这 5 个列表，例如 [o(n*n*n*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：顺便说一句，这不是作业，您可以查看我的其他问题并自己验证。谢谢..

4

2 回答 2

2

受 MRAB 的评论启发，有一个 O(n^3) 解决方案。

首先，将列表 1 中的每个值与列表 2 中的每个值组合起来，并将其存储在一个集合中。调用结果集 1and2，它有 n^2 个值。

接下来，将集合 1and2 与列表 3 组合。调用结果集 1and2and3，它有 n^3 个值，需要 n^3 步来构造。

接下来，组合列表 4 和 5。调用结果集 4and5，它有 n^2 个值。

最后，检查集合 4and5 中的任何值是否等于集合 1and2and3 中的值的倒数。这一步需要 n^2 步。

这种方法使用 O(n^3) 空间和 O(n^3) 时间。

正如 Karoly Horvath 指出的那样，您实际上不需要存储集合 1and2and3，您可以在最后一步从集合 1and2 动态构建它。这种方法仅使用 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()
于 2012-07-19T21:21:16.963 回答
0

如果有 2 个列表，您将从列表 1 中获取一个数字，然后在列表 2 中查找该数字的负数。如果您将列表 2 替换为一个集合，则总体复杂度将为 O(n)。

如果有 3 个列表，您将从列表 1 中获取一个数字，然后从列表 2 中获取一个数字，复杂度为 O(n^2)。如果将列表 3 替换为一组，则总体复杂度为 O(n^2)。

所以我认为 5 个列表/集合的整体复杂性不能降低到 O(n^4) 以下。

于 2012-07-19T14:57:14.927 回答