对坐标向量进行排序C ++

氟利昂3L

我有一个图,其中给定一个节点,我必须生成该图的所有其他节点的有序向量,该向量按最近距离排序。

因此,我有一个包含所有坐标的向量和一个单独的坐标,以将其与所有其他坐标进行比较。我的想法是创建一个地图,该地图将保存任何coordiante(节点)的矢量,所有其他coordiantes均按最接近的位置排序。

我可以使用std :: sort来做到这一点吗?或任何简化此方法的方法?

谢谢

阿西姆·戈亚尔(Aseem Goyal)

我可以使用std :: sort来做到这一点吗?

我认为你走错了方向。如果保留一个带有所有节点坐标的向量,并根据与当前节点的距离对它们进行排序,则它不一定会比较给定向量中的2个坐标!
这是必需的std::sort
为了克服这个问题,您需要预先计算所有节点到给定节点的距离,然后compare()为之定义函数std::sort(),该函数将根据最小距离进行比较。
总时间复杂度:O(N logN)

或任何简化此方法的方法?

相反,有一种更简单的方法。
给定您的节点,使用队列进行广度优先搜索在执行BFS时,您首先访问所有节点,该1节点与原始节点相距一段距离,然后相距一段距离2,依此类推……等等。
总时间复杂度:O(N)

希望这可以帮助 !

本文收集自互联网,转载请注明来源。

如有侵权,请联系 [email protected] 删除。

编辑于
0

我来说两句

0 条评论
登录 后参与评论

相关文章