0

经典的 2sum 问题很简单且众所周知：

你有一个未排序的数组，给你一个值 S。找到数组中所有加起来等于值 S 的元素对。

而且一直有人说，这可以通过在O(N)时间空间复杂度或O(NlogN)时间O(1)空间复杂度上使用HashTable来解决，方法是先排序再左右移动，

好吧，这两个解决方案显然是正确的，但我想不适用于以下数组：

{1,1,1,1,1,1,1,1}

是否可以打印在这个数组中加起来为 2 的所有对O(N)或O(NlogN)时间复杂度？

4

3 回答 3

7

不，打印出所有对（包括重复项）需要O(N2). 原因是因为输出大小是，因此运行时间不能小于那个（因为打印输出中的每个元素需要一些恒定的时间，因此简单地打印输出需要时间）。O(N2)CN2 = O(N2)

如果所有元素都相同，例如{1,1,1,1,1}，则每个可能的对都将在输出中：

1. 1 1
2. 1   1
3. 1     1
4. 1       1
5.   1 1
6.   1   1
7.   1     1
8.     1 1
9.     1   1
10.      1 1

这是N-1 + N-2 + ... + 2 + 1（通过将所有元素都放在右侧的每个元素），即，大于或。
N(N-1)/2 = O(N2)O(N)O(N log N)

但是，您应该能够通过以下方式简单地计算预期的对O(N)：

  • 创建一个哈希映射map，将每个元素映射到它出现的频率。

  • 循环遍历哈希映射并求和，对于每个元素x最多S/2（如果我们向上，S我们将包括该对x和S-x两次，map[x] == 0如果x映射中不存在）：

    • map[x]*map[S-x]if x != S-x（这是选择x和的方法的数量S-x）
    • map[x]*(map[x]-1)/2如果x == S-x（从N(N-1)/2上面）。

当然，您也可以通过创建类似于上面的哈希映射并循环遍历它来打印不同的对，O(N)如果存在则只输出x和S-x值。map[S-x]

于 2013-08-08T15:11:59.583 回答
1

显示或存储结果仅为 O(N 2 )。您突出显示的最坏情况显然有 N 2对，将它们写入屏幕或将它们存储到结果数组中显然至少需要那么多时间。简而言之， 你说的对！

于 2013-08-08T15:33:03.243 回答
0

不

您可以使用排序在O(nlogn)中预先计算它们，但要打印它们，您可能需要的不仅仅是O(nlogn)。在最坏的情况下，它可能是O(N^2)。让我们修改算法以查找所有重复对。

举个例子：

a[ ]={ 2 , 4 , 3 , 2 , 9 , 3 , 3 } and sum =6

排序后：

a[ ] = { 2 , 2 , 3 , 3 , 3 , 4 , 9 }

假设您找到对 {2,4}，现在您必须找到 2 和 4 的计数并将它们相乘以获得重复对。这里 2 出现 2 次，1 出现 1 次。因此 {2,1} 将出现 2 *1 = 输出中的 2 次。现在考虑两个数字相同的特殊情况，然后计算出现次数并将它们平方。这里 { 3,3 } 总和为 6。数组中 3 的出现次数为 3。因此 { 3,3 }将在输出中出现 9 次。

在您的数组 {1,1,1,1,1} 中，只有对 {1,1} 的总和为 2，并且 1 的计数为 5。因此将有 5^2=25 对 {1,1}输出。

于 2015-12-26T15:56:30.107 回答