在二维平面中找到与P点最近的K个点 [英] Find K nearest Points to Point P in 2-dimensional plane

问题描述

资料来源:亚马逊采访问题

Source: AMAZON INTERVIEW QUESTION

在二维空间中给出一个 P点和其他N个点，从与P <最近> 的N个点中找到 K个点

Given a point P and other N points in two dimensional space, find K points out of the N points which are nearest to P.

执行此操作的最佳方法是什么?

What is the most optimal way to do this ?

此 Wiki 页在构建算法方面没有提供太多帮助.任何想法/方法都可以帮助人们. /p>

This Wiki page does not provide much of help in building a algorithm.Any ideas/approaches people.

推荐答案

解决方案1 ​​创建大小为K的堆并以最小的 O(NLogK)复杂度收集点.

Solution 1 make heap of size K and collect points by minimal distance O(NLogK) complexity.

解决方案2 : 取N大小的数组，然后按距离排序.应该使用QuickSort(Hoare修改). 作为答案，请先取得K分. NlogN过于复杂，但是有可能进行优化以逼近O(N). 如果跳过不必要的子数组的排序.当您将数组除以2个子数组时，应仅取第K个索引所在的数组. 复杂度将为:N + N/2 + N/4 + ... = O(N).

Solution 2: Take and array of size N and Sort by distance. Should be used QuickSort (Hoare modification). As answer take first K points. This is too NlogN complexity but it is possible optimize to approximate O(N). If skip sorting of unnecessary sub arrays. When you split array by 2 sub arrays you should take only array where Kth index located. complexity will be : N +N/2 +N/4 + ... = O(N).

解决方案3 :在结果数组中搜索第K个元素，然后减去所有要少的点，然后建立.存在 O(N)算法，类似于对中位数的搜索.

Solution 3: search Kth element in result array and takes all point lesser then founded. Exists O(N) alghoritm, similar to search of median.

注意事项:最好使用距离的sqr以避免sqrt操作，如果点具有整数坐标，则速度会更快.

Notes: better use sqr of distance to avoid of sqrt operations, it will be greater faster if point has integer coordinates.

面试回答最好使用解决方案2或3.

As interview answer better use Solution 2 or 3.

这篇关于在二维平面中找到与P点最近的K个点的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！