4

对于给定的一组数字

3 5 3 6 3 4 10 4 5 2

我希望找到所有**triplets**形成算术级数的元素。

like (3,3,3) (3,4,5) (6,4,2) (3,4,5)

我有一个简单的 O(n^3) 解决方案。我想知道是否可以在 O(n^2) 或更短的时间内完成。

非常感谢任何帮助。

4

2 回答 2

5

O(n^2 * logn)可以通过以下方式实现:

  1. 对数组进行排序 - O(nlogn)
  2. 迭代所有对(其中的O(n ^ 2)) - 并对每对(x,y)进行二进制搜索,看看你是否有:max{x,y} + abs(x-y)min{x,y} - abs(x-y)作为一个元素。
    应特别注意对x==y- 但它可以在相同的时间复杂度内轻松解决。

请注意,此解决方案将为您提供每个三元组出现 1 次(无重复)。

编辑:通过使用哈希表(如果您关心三元组的数量,则使用直方图)并查看它而不是对数组进行排序并使用二进制搜索 - 您可以O(n^2)平均减少时间,但会O(n)增加额外空间的成本)。


如果没有 1 次出现的缺点 - 它不能做得更好O(n^3),因为可能有O(n^3)这样的三元组,例如在数组中[1,1,1,...,1]- 你有chose(3,n)这样的三元组。

于 2012-11-10T09:14:12.807 回答
1

可以使用散列来解决它,方法O(n^2)是选择一个中间元素,然后选择 中的第一个和最后一个元素O(n)

这是一个简单的问题,即在一个总和固定的数组中找到两个数字。在这里,a+c应该是2b

因此,我所寻找的都是a&c这样的a+c=2i

于 2015-09-16T14:31:23.393 回答