解决方案1制作大小为 K 的堆并按最小距离收集点O(NLogK)复杂。
解决方案2：
取大小为 N 的数组并按距离排序。应该使用QuickSort（霍尔修改）。
取前 K 点作为答案。
这太复杂了 NlogN，但可以优化到近似 O(N)。
如果跳过不必要的子数组的排序。当您将数组分割为 2 个子数组时，您应该仅采用第 K 个索引所在的数组。
复杂度为：N +N/2 +N/4 + ... =O(N).
解决方案3：搜索结果数组中的第 K 个元素，并取所有小于找到的点。存在O(N)算法，类似于中值搜索。
Notes：最好使用距离的平方来避免 sqrt 运算，如果点是整数坐标，速度会更快。
作为面试答案，最好使用解决方案 2 或 3。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
