给定一组整数，问题在于找到长度为 3 的可能算术级数的数量。整数集可能已排序，也可能未排序。
我可以实现一个简单的蛮力算法，花费时间 O(n^3)，但时间效率很重要，整数集可以大到 10^5。这意味着暴力破解显然行不通。任何人都可以在 C++ 中建议一些算法/伪代码/代码吗？
一个例子：有 4 个数字 5,2,7,8 。显然只有一种可能性 - (2,5,8)，其中公差为 3，所以我们的答案是 1。
编辑：我忘了提到一个重要的属性 - 每个给定的集合数在 1 到 30000 之间（包括）。
问问题
1855 次
2 回答
4
您可以在 O(N^2) 中执行以下操作：创建整数的哈希集，以便您可以检查O(1). 之后，在所有成对的集合元素上创建两个嵌套循环{X, Y}。这是在O(N^2).
对于每一对{X, Y}，假设X < Y，并计算两个数：
Z1 = X - (Y-X)
Z2 = Y + (Y-X)
三元组{X, Y, Zi}形成一个算术序列如果Zi != X && Zi != Y && set.contains(Zi)
检查三元组{X, Y, Z1}和{X, Y, Z2}. 您可以O(1)使用哈希集来完成，算法的总运行时间为O(N^2).
于 2012-11-10T18:36:05.320 回答
3
O(N+BlogB) 的替代解决方案（其中 B 是整数的最大大小 - 在您的情况下为 30,000）是考虑直方图 H，其中 H[x] 是 x 在序列中出现的次数.
这个直方图可以在时间 N 中计算出来。
您正在寻找元素 a,b,c 使得 ba=cb。这等价于 2b=a+c。
所以想法是计算 a+c 的第二个直方图 G[x]，然后遍历所有元素 b 并将 H[b]*G[2b] 添加到总数中。这需要时间 O(B)。
（G[x] 是序列中有一对值 a,b 使得 x=a+b 的次数。）
唯一的困难是计算 G[x]，但这可以使用快速傅里叶变换在 O(BlogB) 时间内将 H[x] 与自身进行卷积来完成。
于 2012-11-10T20:54:25.863 回答