对于给定的一组数字
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) 或更短的时间内完成。
非常感谢任何帮助。
2208 次
2 回答
5
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 次（无重复）。
（编辑：通过使用哈希表（如果您关心三元组的数量，则使用直方图）并查看它而不是对数组进行排序并使用二进制搜索 - 您可以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 回答