0

我被要求为这个问题编写算法：给定数组 A，我们想知道数组中是否存在 U+L=K 的任何两个元素 U 和 L

我这样写我的算法：

while(first<last)
{
  if(arr[first]+arr[last]==k)
     return true
  else if(arr[first]+arr[last]<k)
     last=last-1;
  else
     first++;
}
return false   

}

但问题是这个算法的运行时间是多少？是 O(nlogn) 吗？如果是，为什么？如果不是，我如何在 O(nlogn) 中实现它？

4

2 回答 2

1

你的算法的运行时间是O(N)因为在最坏的情况下，你最终会迭代整个数组。

尽管您的算法无法解决问题。例如考虑{9,1,3,4,2}. 在这种情况下 if kwould be 12，它将返回 false。对于您的算法，应首先对输入数组进行排序，然后将其传递给算法，这将O(NlogN)在最坏的情况下进行。

然而，一个更快的解决方案是使用类似HashMap的东西及时解决问题O(N)。

于 2013-10-20T19:59:33.667 回答
1

这是python中alg的一个小例子，结果为false，但列表中有两个元素满足U+L=k

def testArray(a, k):
    first = 0
    last = len(a) - 1

    while (first < last):
        print first, last
        if (a[first] + a[last] == k):
            return True
        elif (a[first] + a[last] < k):
            last=last-1
        else:
            first=first+1
    return False

a = [3, 1, 5, 3, 6]
print testArray(a, 6)
于 2013-10-20T20:09:32.563 回答