在二维空间中找到最近的点

如果数组没有以任何方式进行排序,那么就不可能比O(n)更快,因为您必须检查每个点,以确保它不比您迄今为止找到的任何点更接近。

你可以使用 Bounding Volume Hierarchy . 但这并不能改善最坏情况下的复杂性,也不能直接得到精确的解决方案。

如果这些点是在x坐标上排序的,我得到了一个O(logN)的解。

考虑2D情况。

假设每个点用以下数据结构表示:

class Point {
    public float getX();
    public float getY();
}

ARRAY ,和另一个点 D

D级 D级 .

int pivotIndex = partition(array, 0, array.length() - 1, d);

pivotIndex x坐标小于 d.getX() 数据透视索引 x坐标等于或大于 d、 getX()

如果所有的点都在 数据透视索引 会是 array.length() - 1 D级 数据透视索引 会是 -1 . 如果一些点在 D级 D级 ,那么 将介于 0 数组长度() - 1 . 对于x坐标与 D级 ,他们被认为是在“右边”。

Point p1 = getNearestDot(array, 0, pivotIndex, d);
Point p2 = getNearestDot(array, pivotIndex + 1, array.length() - 1, d);

if (p1 == null) return p2;
if (p2 == null) return p1;

return nearer(p1, p2, d);

数组 在左边 D级 ,则在本例中p2将为null。同样,如果 在…的右边 D级 ,则p1将为空。

算法 getNearestDot

// Find the nearest dot in array[low...high] inclusive which is closest to point d 
Point getNearestDot(Point[] array, int low, int high, Point d) {
    if (low > high)
        return null;
    if (low == high)
        return array[low];

    int middle = low + (high - low) >> 1;
    Point p1 = getNearestDot(array, low, middle, d);
    Point p2 = getNearestDot(array, middle + 1, high, d);

    if (p1 == null) return p2;
    if (p2 == null) return p1;

    return nearer(p1, p2, d);
} 

实际上,我们可以在x坐标中对点进行排序,然后从x差最接近目标的点开始,向左和向右扫描,一旦下一个点在该方向上的x差已经大于目前为止发现的最小距离,就停止向一个方向扫描。 分而治之仍然是线性的,如果你分成两半,但不放弃任何一半。