我们如何找到距离原点最近的 K 个点，并在考虑距离相等的情况下根据 x 坐标进行排序？

Question

我们得到了一堆 (x, y) 坐标，我们需要找到离原点最近的 K 个点。当我们找到几个与原点距离相等的点并且我们需要在其中一些点之间进行考虑时，我们取 x 坐标最小的点。如果两个 x 坐标相同（这意味着 2 个点相等）- 我们取其中一个。

例如 - 我们给出 (1,1), (-2,3), (2, 3) 和 K = 2

所以，答案是 (1,1) 和 (-2, 3)。

我的方法是 - 在原始点列表中生成距离与位置之间的地图。然后获取一系列距离并对其进行排序。然后我们获取新排序数组中的每个距离并从地图中提取所有键（因此原始数组中的位置），如果它们大于 1 并且我们还没有达到 K -> 我们检查 x 坐标并将其添加到结果中。但是我无法正确地实现这一点，我认为这不是最有效的方法。

Answer 1

您不需要找到所有的距离并对它们进行排序。保持最大 K 长度的最大堆就足够了。您可以将 x 坐标作为堆排序算法的第二个参数。

这是一个 python 问题的解决方案，您几乎可以将其视为伪代码：

import heapq

hp = []
for x, y in coordinates:
  dist = x**2 + y**2
  heapq.heappush(hp, (-dist, -x, y))
  if len(hp) >= K:
    heapq.heappop(hp)

res = [(-x, y) for d, x, y in hp]

请注意，我们可以在 len(hp) >= k 时使用 heapq.heappushpop。这稍微更有效，但它不是重点，因为它是特定于实现的。

我们是这样做的：

将 (dist, x, y) 的元组压入堆中。请注意，由于 python 的默认堆实现是最小堆，我们需要取反距离和 x 坐标，以便较大的距离和 x 坐标位于堆的顶部。
每当堆的长度 >= K 时，我们弹出一个。这确保了具有最长距离的坐标首先被弹出（因为它是一个最小堆并且我们正在否定距离）。它还确保在平局的情况下，首先弹出较大的 x 坐标。
最后我们从堆中提取坐标，确保取反 x 坐标。

这个算法的时间复杂度是O(n * log k)，其中n是坐标列表的长度，k是我们想要的坐标数。

space 复杂度为 k。

Answer 2

替代方法将 Balltree. It can query 最近的 K 点。我先生成10K个随机点，整数。

import numpy as np
from sklearn.neighbors import BallTree

points = np.floor(np.random.normal(size=(10000,2), loc=(25,25), scale=(16,16)))

K = 12

创建一棵树，并查询它以找到最近的 K 点，到 (0,0)。

tree = BallTree(points, leaf_size=10, metric='euclidean')

distances, indici = tree.query( np.array([[0,0]]), k=K,return_distance=True)

创建一个 (distance, point) 元组，以便以后可以随意排序。

close_points_as_list = [ (x,y) for (x,y) in points[indici].tolist()[0] ]
distances_as_list = distances.tolist()[0]

distances_points_tuples = list(zip(distances_as_list, close_points_as_list))

对于列表distances_points_tuples中的p，p[0]是到(0,0)的距离，p[1][0]是x，p[1][1]是y.

我不确定 'smallest' x 是什么。注意我使用 x 的 np.abs() 来定义二级排序。

sorted_points = sorted(distances_points_tuples, key=lambda x: (x[0], np.abs(x[1][0])) )

import pprint

pprint.pprint(sorted_points)

会给

[(0.0, (0.0, 0.0)),
 (1.4142135623730951, (1.0, -1.0)),
 (1.4142135623730951, (-1.0, -1.0)),
 (1.4142135623730951, (-1.0, 1.0)),
 (1.4142135623730951, (-1.0, 1.0)),
 (2.0, (0.0, -2.0)),
 (2.0, (0.0, 2.0)),
 (2.23606797749979, (-1.0, -2.0)),
 (2.23606797749979, (2.0, 1.0)),
 (2.23606797749979, (-2.0, 1.0)),
 (2.23606797749979, (-2.0, -1.0)),
 (2.23606797749979, (-2.0, 1.0))]

我们如何找到距离原点最近的 K 个点，并在考虑距离相等的情况下根据 x 坐标进行排序？

How can we find K closest points to the origin, and sort based on x-coordinates when there's equal distances to consider?

sorting

algorithm

heap

hashmap