K个最近的点。时间复杂度为O（n），而不是O（nLogn）。如何做到的？

Question

如果给你一百万个坐标，形式上与谷歌地图的经纬度相同，那么你该如何打印出距离给定位置最近的k个城市？

我在面试中被问到这个问题。面试官说可以使用插入排序来找到最近的k个城市，时间复杂度为O(n)，而不是对整个列表进行排序，时间复杂度为NlogN。我在网上找到其他答案，大多数都说时间复杂度为NLogN……他[面试官]的答案正确吗？

- user3259176

---

我认为你的面试官是正确的。 - RBarryYoung

如果k是一个固定的数字，那么是O(n)。如果k是一个参数，那么是O(n*k)。 - Arturo Menchaca

有多种不同的方法来跟踪前k个答案，请参见https://dev59.com/YWIk5IYBdhLWcg3wfOOe。 - mcdowella

Answer 1

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

每当有新的距离时，如果它小于最大值，则将其插入列表中并删除最大值。

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

在最坏的情况下，您将插入n次。总体而言，它将是O(NK)或O(NlogK)。如果K足够小，则为O(N)。

- Hanqiu Zhang

Answer 2

这是一个快速选择算法(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)。

- maxim1000

Answer 3

假设纬度和经度有一定数量的数字，我们实际上可以使用基数排序。它似乎类似于Hanqiu的答案，但我不确定是否是同一个。维基百科描述：

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

该文章关于效率的内容如下：

与其他排序算法相比的基数排序效率问题有些棘手，容易引起很多误解。无论基数排序是否与最佳比较排序算法一样有效、不如有效或更有效，都取决于所做的假设细节。对于大小为w位的整数键值n个，基数排序的复杂度为O(wn)。有时w被视为一个常数，这将使基数排序在“足够大”的情况下比所有执行Θ(n log n)次比较以排序n个键的比较排序算法更好。

在您的案例中，w对应于纬度和经度的字长，也就是数字的数量。特别是在您的坐标精度较低（数字较少）时，这变得更加高效。无论是否比nlogn算法更有效，都取决于您的n和实现方式。在渐近意义上，它比nlogn更好。

显然，你仍然需要将这两种算法组合成实际距离。

- JJJ

Answer 4

你也可以使用这个算法，它具有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);
}

这个想法是循环遍历城市列表，计算与感兴趣的坐标之间的距离，然后使用距离来确定应该将城市添加到类似于“哈希映射”的数组cityDistances中的位置。距离越小，索引就越接近0。
resolution越小，最后一次循环后列表closestCities中有10个城市的可能性就越大。

- Maljam