在二维平面中找到K最近点到点P.

解决方案1使堆大小为K并通过最小距离O(NLogK)复杂度收集点.

解决方案2:获取大小为N的数组并按距离排序.应该使用QuickSort(Hoare修改).作为答案采取前K点.这也是NlogN的复杂性,但可以优化以近似O(N).如果跳过不必要的子数组的排序.当您将数组拆分为2个子数组时,您应该只接受Kth索引所在的数组.复杂度将是:N + N/2 + N/4 + ... = O(N).

解决方案3:在结果数组中搜索Kth元素并获取所有小点然后建立.存在O(N) alghoritm,类似于搜索中位数.

注意:最好使用sqr of distance来避免sqrt操作,如果point有整数坐标,它会更快.

面试答案更好地使用解决方案2或3.

只需一个查询...

保持一堆大小k.

对于每个点,计算到该点的距离P.将该距离插入堆中,如果堆的大小大于,则从堆中删除最大值k.

运行时间: O(n log k)