对于给定的一组数字
3 5 3 6 3 4 10 4 5 2
我希望找到构成等差级数的所有**三元组**
。
like (3,3,3) (3,4,5) (6,4,2) (3,4,5)
我有一个简单的 O(n^3) 解决方案。我想知道是否可以在 O(n^2) 或更短的时间内完成。
非常感谢任何帮助。
最佳答案
O(n^2 * logn)
可以通过以下方式实现:
- 对数组进行排序 - O(nlogn)
- 迭代所有对(其中 O(n^2) 个)- 对每对 (x,y) 进行二分搜索以查看是否有:
max{x,y} + abs(x-y)
或min{x,y} - abs(x-y)
作为一个元素。
应特别注意x==y
的对 - 但它可以在相同的时间复杂度内轻松解决。
请注意,此解决方案将为您提供每个三元组出现 1 次(无重复)。
(编辑:通过使用哈希表(histogram 如果您关心三元组的数量)并查看它而不是对数组进行排序和使用二进制搜索 - 您可以减少时间平均为 O(n^2)
,额外空间为 O(n)
。
没有 1 次出现的缺点 - 它不能比 O(n^3)
做得更好,因为可能有 O(n^3)
这样的三元组,对于数组 [1,1,1,...,1]
中的示例 - 您有 choose(3,n)
这样的三元组。
关于algorithm - 数字列表中的算术序列,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/13320734/