给定一组整数,问题包括找到长度为 3 的可能算术级数的数量。整数集可能已排序,也可能未排序。
我可以实现一个简单的暴力破解算法,耗时 O(n^3),但时间效率很重要,整数集可以大到 10^5。这意味着暴力破解显然行不通。任何人都可以用 c++ 推荐一些算法/伪代码/代码吗?
例如:有 4 个数字 5,2,7,8 。显然只有一种这样的可能性 - (2,5,8) 其中公差为 3,所以我们的答案是 1。
编辑:我忘了提及一个重要属性 - 给定的每个集合数都在 1 到 30000 之间(含)。
最佳答案
您可以按如下方式在 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)
.
关于algorithm - 在给定的一组数字中找出可能的等差数列 3 的个数,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/13324832/