K最近点。时间复杂度O（n），而不是O（nLogn）。怎样

Question

就像谷歌地图一样，给定一百万个经纬度坐标列表，你将如何打印距离给定位置最近的k个城市？

我在一次面试中问了这个问题。面试官说这可以在O（n）中通过使用插入排序到k来完成，而不是对整个列表进行排序，即NlogN。我在网上找到了其他答案，大多数人都说NLogN...他[面试官]正确吗？

Answer 1

假设经纬度有给定的位数，我们实际上可以使用基数排序。这似乎与韩秋的答案相似，但我不确定是否是同一个答案。维基百科描述：

在计算机科学中，基数排序是一种非比较整数排序算法，它通过按共享相同有效位置和值的单个数字对键进行分组，对具有整数键的数据进行排序。需要位置表示法，但由于整数可以表示字符串（例如名称或日期）和特殊格式的浮点数，基数排序不限于整数。基数排序可以追溯到1887年赫尔曼·霍勒瑞斯在制表机上的工作。

关于效率，文章说了以下几点：

与其他排序算法相比，基数排序的效率这一主题有些棘手，容易引起很多误解。与基于比较的最佳算法相比，基数排序是否同样有效、效率更低或效率更高，取决于所做假设的细节。对于字长为w的整数的n个键，基数排序复杂度为O（wn）。有时w表示为常数，这将使基数排序比基于比较的最佳排序算法更好（对于足够大的n），这些算法都执行Θ（n log n）比较以对n个键进行排序。

在您的情况下，w对应于您的纬度和经度的单词大小，即位数。特别是，对于坐标中较低的精度（较少的数字），这会变得更有效。nlogn算法是否更有效取决于您的n和您的实现。渐近地说，它比nlogn更好。

显然，您仍然需要将两者结合到实际距离中。

Answer 2

这是一个quickselect算法(https://en.wikipedia.org/wiki/Quickselect)

基本上，它是一种经过修改的快速排序-每当你有两个半部分时，你只对其中一个进行排序：

• 如果一半包含第k个位置-继续细分和排序
• 如果一半完全在第k个位置之后-不需要对其进行排序，我们对那些元素不感兴趣
• 如果一个半完全在第k个位置之前-不需要对其进行排序，我们需要所有这些元素，它们的顺序并不重要

完成后，您将在数组的前k个位置拥有最接近的k个元素（但它们不一定排序）。

因为每一步只处理一半，所以时间将是n/2 n/4 n/8=2n（忽略常量）。

对于保证的O（n），您始终可以选择一个好的枢轴，例如中间带(https://en.wikipedia.org/wiki/Median_of_medians).

Answer 3

我认为，在计算距离时，您可以维护K个元素的列表。

每次有新距离时，如果该距离小于最大距离，请将其插入列表，然后删除最大距离。

如果您使用的是排序数组，则此插入可以是O（k），如果您使用的是二进制堆，则可以是O（logK）。

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