对于给定的一组数字
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) 或更短的时间内完成。
非常感谢任何帮助。
O(n^2 * logn)
可以通过以下方式实现:
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)
这样的三元组。
可以使用散列来解决它,方法O(n^2)
是选择一个中间元素,然后选择 中的第一个和最后一个元素O(n)
。
这是一个简单的问题,即在一个总和固定的数组中找到两个数字。在这里,a+c
应该是2b
。
因此,我所寻找的都是a
&c
这样的a+c=2i
。