[算法] 已知在平面坐标系内有N个点,求离开给定坐标距离最近的10个点

时间:2020-12-28 09:54:46

最近在工作中碰到了这个问题:已知在平面坐标系内有N个点,求离开给定坐标距离最近的10个点。

团队的第一反应自然是按照两点间距离公式, 遍历N个已知点,然后排序获得前10个最短距离的结果。

 只是,我从来不是一个规规矩矩的人。我一直推崇用人类直觉思维来编程,而不要被僵化的程序思想束缚。

传统距离公式,计算N个点的距离需要2N次的减法和平方。

而事实上, 一个真正的人类,是不会把所有N个点的距离都计算一遍的。大多数点都会被某些快速条件过滤掉的。

今天先把问题在这里写下来, 有时间在把优化后的算法补充进来。

最差劲模式
每次遍历已知点数组,逐个计算两点间距离,保留最小值以及索引信息。

时间复杂度 O(n)

缺点:每次查询都要重新遍历数组,效率低下。

优化模式1:

dic3提出的方式

预处理阶段,遍历所有已知点,得出一个初始化半径,以确保至少能有一个或多个点在半径内。

实际处理阶段:

用初始化半径,判断半径内的已知点。然后根据结果再次扩大或缩小半径。

缺点:严重的问题是,如何知道半径内的点都是谁?其实又要遍历所有点了。

优化模式2:网格预处理

预处理阶段,按已知坐标将所有点分配到二维数组内

实际处理阶段:

按目标坐标计算并获取核心下标,获得二维数组内的一个元素

判断这个网格内的所有点的距离并获取结果。

如果目标点在网格边缘,需要进一步增加相邻网格内的数据来判断。

缺点:

1、最差情况下要判断4个网格

2、当网格内元素数量持续增加时,算法效率同样下降明显。

时间复杂度 O(n/网格数量)