我有一个包含纬度和经度的数组。任务是找到所有坐标的5个最近的坐标，而不是每次都循环遍历所有坐标。
有几种解决方案，具体取决于您的数据（您对此一无所知）以及您想要的确定程度。
- 如果您的数据是均匀分布的，那么您可以在数据之上创建一个网格并将点分配给该网格。之后，对于每个元素，您找出它属于哪个网格，并比较该网格（以及最近的网格）中的距离。通过良好的网格选择并假设网格中平均有 k 个元素，这可以为您提供潜在的
O(n * k^2)运行时间。看看这个答案更多解释 https://stackoverflow.com/a/4172378/1090562.
- 对数据一无所知，您可以构造一个2-d tree https://en.wikipedia.org/wiki/K-d_tree在 O(n log n) 时间内，然后对于数据库中的每个点询问距它最近的点是什么（您在 O(logn) 中询问总共 n 个点）。所以总复杂度是
O(n log n )
- 另一种方法是使用概率方法，称为局部敏感度散列 https://en.wikipedia.org/wiki/Locality-sensitive_hashing#LSH_algorithm_for_nearest_neighbor_search。维基页面太复杂了，即使知道这是什么，我也很难阅读该页面。看一眼这个描述 http://infolab.stanford.edu/~ullman/mmds/ch3a.pdf为了更好地理解它。
- @Gene 建议使用另一种方法quadtree https://en.wikipedia.org/wiki/Quadtree（没有听说过这种树，所以将其留空）
所以正如你所看到的，有可能比O(n^2)这项任务的复杂性。
所有方法都描述了如何找到距离您正在搜索的点最近的点。很明显，找到最近的点后，您可以将其删除并找到另一个最近的点，依此类推，直到找到与您的点最接近的 5 个点。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
