给定一个以经度和纬度为形式的百万坐标列表，就像谷歌地图一样，你将如何打印离给定位置最近的k个城市？
我在一次采访中被问到这个问题。采访者说，这可以在O（n）中完成，方法是使用插入排序到k，而不是对整个列表进行排序，即NlogN。我在网上找到了其他答案，大多数人说NLogN。。。他（面试官）说得对吗？
我认为，在计算距离时，可以维护一个K元素的列表。
每次有新距离时，如果它小于最大距离，请将其插入列表，然后删除最大距离。
如果使用排序数组，则此插入可以是O（k）；如果使用二进制堆，则此输入可以为O（logK）。
在最坏的情况下，您将插入n次。总的来说，它将是O（NK）或O（NlogK）。如果K足够小，它就是O（N）。
这是一种快速选择算法(https://en.wikipedia.org/wiki/Quickselect)
基本上，它是带修改的快速排序——每当你有两半时，你只对其中一个进行排序：
- 如果一半包含第k个位置-继续细分和排序
- 如果一半完全在第k个位置之后-无需对其进行排序，我们对这些元素不感兴趣
- 如果一半完全在第k个位置之前-无需排序，我们需要所有这些元素，它们的顺序无关紧要
完成后，您将在数组的前k个位置拥有最接近的k个元素（但它们不一定是排序的）。
由于每一步只处理一半，时间将是n+n/2+n/4+n/8+...=2n（忽略常量）。
对于有保证的O(n)，您总是可以选择一个好的枢轴，例如中位数(https://en.wikipedia.org/wiki/Median_of_medians)。
假设纬度和经度有一定数量的数字，我们实际上可以使用基数排序。这似乎与韩秋的答案相似，但我不确定它是否是同一个。维基百科描述：
在计算机科学中，基数排序是一种非比较整数排序算法，它通过按共享相同有效位置和值的单个数字对关键字进行分组，来对具有整数关键字的数据进行排序。位置表示法是必需的，但由于整数可以表示字符串（例如，名称或日期）和特殊格式的浮点数，基数排序不限于整数。Radix排序可以追溯到1887年赫尔曼·霍勒里斯在制表机上的工作。
文章介绍了以下关于效率的内容：
与其他排序算法相比，基数排序的效率这个话题有些棘手，而且容易引起很多误解。基数排序的效率是否与基于最佳比较的算法相同、更低或更高取决于所做假设的细节。对于n个字大小为w的整数的键，基数排序的复杂度为O（wn）。有时w被表示为常数，这将使基数排序（对于足够大的n）比基于最佳比较的排序算法更好，后者都执行Θ（n-logn）比较来对n个键进行排序。
在您的情况下，w对应于您的纬度和经度的单词大小，即数字数量。特别是，对于坐标中较低的精度（较少的数字），这会更有效。nlogn算法是否更有效取决于您的n和您的实现。渐进地，它比nlogn好。
显然，你仍然需要将两者结合成实际距离。
您也可以使用具有O（N）复杂性的此算法，它利用了一个"类似HashMap"的数组，该数组将在给定的分辨率内自动对距离进行排序。
以下是Java中的伪代码：
City[] cities = //your city list
Coordinate coor = //the coordinate of interest
double resolution = 0.1, capacity = 1000;
ArrayList<City>[] cityDistances = new ArrayList<City>[(int)(capacity/resolution)];
ArrayList<City> closestCities = new ArrayList<City>();
for(City c : cities) {
double distance = coor.getDistance(c);
int hash = distance/resolution;
if(cityDistances[hash] == null) cityDistances[hash] = new ArrayList<City>();
cityDistances[hash].add(c);
}
for(int index = 0 ; closestCities.size() < 10 ; index++) {
ArrayList<City> cList = cityDist[index];
if(cList == null) continue;
closestCities.addAll(cList);
}
其想法是循环浏览城市列表，计算具有感兴趣坐标的距离，然后使用该距离来确定城市应添加到"类似HashMap"的数组cityDistances中的位置。距离越小，索引就越接近0。resolution越小，列表closestCities在最后一个循环后最终有10个城市的可能性就越大。