logo标签列表

给定n个点，右角三角形的数量

algorithm
3

在xy平面上给定n个点，我需要找到使用这些点作为顶点可以形成的直角三角形数。我想知道一个更优的解决方案，而我已经想出了一个O(n3)解决方案，其中每次取3个顶点并检查它们是否形成一个直角三角形。

n 有任何限制条件吗？ - Pham Trung
我投票关闭此问题，因为它要求算法并且没有具体的编程问题。 - Brian Agnew
@PhamTrung 不是的。我只想知道最优解决方案。 - shreyansh
1个回答
6

一种O(n^2)的解决方案可能是这样的：

  • 逐个遍历每个点，
  • 当处理每个点时，计算由该点和列表中其他点形成的单位向量；然后将它们存储在HashMap中。对于这些向量中的每一个，计算与之成直角的单位向量，并在HashMap中查找。
你的解决方案在理论上相当优雅。但是当你对向量进行归一化时，你忽略了向量的长度。勾股定理基于直角三角形的边长，这意味着你确实需要考虑长度。即使你修改算法来处理它们，也会增加你提供的解决方案的时间复杂度。 - ilim
@ilim，为什么你需要长度来判断两个向量是否垂直？ - SaiBot
@ilim，我想你不需要考虑长度 :thinking: ? 你可以使用点积属性进行计算。 - Pham Trung
@PhamTrung 看起来我误解了你对HashMap的使用。你是正确的。我还没有考虑过正式的证明，但你的算法看起来是可行的。 - ilim
@PhamTrung 你是否将每个单位向量的频率与其存储在HashMap中？ - shreyansh
@shreyansh 是的，应该没问题。 - Pham Trung
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接