algorithm - K个最近的点。时间复杂度 O(n)，而不是 O(nLogn)。如何？

Question

给定一百万个经度和纬度形式的坐标列表，就像 Google map 一样，您将如何打印离给定位置最近的 k 个城市？

我在面试中被问到这个问题。面试官说这可以在 O(n) 中完成，方法是使用最多 k 的插入排序，而不是对整个列表进行排序，即 NlogN。我在网上找到了其他答案，大多数人说 NLogN ......他[采访者]是对的吗？

Answer 1

我觉得，在计算距离的时候，可以维护一个K个元素的列表。

每次你有一个新的距离，如果它比最大的距离小，就将它插入到列表中，并移除最大的距离。

如果您使用排序数组，则此插入可以是 O(k)，如果您使用二叉堆，则此插入可以是 O(logK)。

在最坏的情况下，你会插入n次。总的来说，它将是 O(NK) 或 O(NlogK)。如果K足够小，就是O(N)。