一面试题，大家来试试最优解法

Question

面试题 分治法 最近坐标

Answer 1

最差劲模式：
每次遍历已知点数组，逐个计算两点间距离，保留最小值以及索引信息。时间复杂度 O(n)缺点：每次查询都要重新遍历数组，效率低下。优化模式1：dic3提出的方式预处理阶段，遍历所有已知点，得出一个初始化半径，以确保至少能有一个或多个点在半径内。实际处理阶段：用初始化半径，判断半径内的已知点。然后根据结果再次扩大或缩小半径。缺点：严重的问题是，如何知道半径内的点都是谁？其实又要遍历所有点了。优化模式2：网格预处理预处理阶段，按已知坐标将所有点分配到二维数组内实际处理阶段：按目标坐标计算并获取核心下标，获得二维数组内的一个元素判断这个网格内的所有点的距离并获取结果。如果目标点在网格边缘，需要进一步增加相邻网格内的数据来判断。缺点：1、最差情况下要判断4个网格2、当网格内元素数量持续增加时，算法效率同样下降明显。时间复杂度 O(n/网格数量)

Answer 2

我就不写代码了哈，就说说我的思路：随便选定一点A点坐标，然后以指定坐标为圆心O，以圆心到A的距离为半径，画圆，判断是否有坐标点在圆内或者圆上，一找到，再以这点到O的距离为半径，直到在圆内找不到为止，那么这时在圆上的点就是距离最近的点

Answer 3

    对每个点都要进行两次POW和一次SQR，还要进行数据类型的转化，速度比较慢。可以对数据进行预处理：首先计算两点间的x、y距离差分别为（X1，y1），求最小（X+Y），根据三角形定律两边和大于第三边，这个X+Y肯定大于两点间距离，求出这个X+Y以后，所有X距离或Y距离大于这个X+Y的都可以排除了。这样范围能缩到很小。复杂度O（2n）但是运算量大大缩小了。
    

Answer 4

“不全部遍历所有坐标点”是不可能的。任何一种预处理（比如说按照x和y排序）都需要遍历所有坐标点。不进行预处理，什么“把坐标分成两部分”这就是不合逻辑的话。实际上，假设你计算出来第一个参考点距离目标点的距离是a，那么你只需要过滤剩下 x<=a && y<=a 的点了，其它的点就可以删除掉了。如果所有点都被删除掉了，那么这个参考点就是要找的。否则可以迭代这个做法。

Answer 5

先算出一点的距离 L, 
然后遍历,
判断, Xn-X0 或 Yn-Y0 的绝对值是否大于L
大于L,进下一点
小于等L,计算实际距离Ln
判断Ln与L的值,根据情况接着处理这样处理地,应该会比楼主的效率要高,

Answer 6

一次性的查找只能循环遍历。
面试官应该需要的是能够重复使用的查询调用，可使用KD tree或者Rtree之类的数据结构。

Answer 7

其他的不说，其实要测算最近距离，根本不用 Math.Sqrt。平方和大，Math.Sqrt 一定大。你觉得是不是？所以这步 Sqrt 多余的，而且影响性能

Answer 8

不遍历 没法做 
分治算法如下  
首先划分集合S为SL和SR，使得SL中的每一个点位于SR中每一个点的左边，并且SL和SR中点数相同。分别在SL和SR中解决最近点对问题，得到DL和DR，分别表示SL和SR中的最近点对的距离。令d=min(DL,DR)。如果S中的最近点对(P1,P2)。P1、P2两点一个在SL和一个在SR中，那么P1和P2一定在以L为中心的间隙内，以L-d和L+d为界，如下图所示：                            如果在SL中的点P和在SR中的点Q成为最近点对，那么P和Q的距离必定小于d。因此对间隙中的每一个点，在合并步骤中，只需要检验yp+d和yp-d内的点即可。步骤1：根据点的y值和x值对S中的点排序。步骤2：找出中线L将S划分为SL和SR步骤3：将步骤2递归的应用解决SL和SR的最近点对问题，并令d=min(dL,dR)。步骤4：将L-d~L+d内的点以y值排序，对于每一个点(x1,y1)找出y值在y1-d~y1+d内的所有点，计算距离为d'。                 如果d'小于d，令d=d'，最后的d值就是答案。

Answer 9

“不全部遍历所有坐标点”是不可能的。任何一种预处理（比如说按照x和y排序）都需要遍历所有坐标点。不进行预处理，什么“把坐标分成两部分”这就是不合逻辑的话。
 
实际上，假设你计算出来第一个参考点距离目标点的距离是a，那么你只需要过滤剩下 x<=a && y<=a 的点了，其它的点就可以删除掉了。
 
如果所有点都被删除掉了，那么这个参考点就是要找的。
 
否则可以迭代这个做法。