我們得到了一堆 (x, y) 坐標，我們需要找到到原點的 K 最接近點。當我們找到幾個與原點距離相等的點，需要在其中一些點之間進行考慮時，我們取x坐標最小的點。如果兩個 x 坐標相同（這意味著 2 個點相等） - 我們取其中一個。
例如 - 我們給定 (1,1), (-2,3), (2, 3) 和 K = 2
所以，答案是 (1,1) 和 (-2, 3)。
我的方法是 - 在原始點串列中生成距離與位置之間的地圖。然后獲取一系列距離并對其進行排序。然后我們獲取新排序陣列中的每個距離并從地圖中提取所有鍵（因此是原始陣列中的位置），如果它們大于 1 并且我們還沒有達到 K -> 我們檢查 x 坐標并將其添加到結果中。但我無法正確實作這一點，我認為這不是最有效的方法。
uj5u.com熱心網友回復：
您不需要找到所有距離并對它們進行排序。保持最多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]
請注意，我們可以使用heapq.heappushpopwhen len(hp) >= k。這稍微更有效，但它無關緊要，因為它是特定于實作的。
這是我們要做的：
- 在堆上推送 (dist, x, y) 的元組。請注意，由于 python 的默認堆實作是最小堆，我們需要對距離和 x 坐標取反，以便較大的距離和 x 坐標位于堆的頂部。
- 每當堆的長度 >= K 時，我們就彈出一個。這確保了具有最長距離的坐標首先被彈出（因為它是一個最小堆并且我們正在否定距離）。它還確保在出現平局的情況下，首先彈出較大的 x 坐標。
- 最后，我們從堆中提取坐標，確保否定 x 坐標。
這個演算法的時間復雜度是O(n * log k)哪里n是坐標串列的長度，k是我們想要的坐標數量。
空間復雜度為k。
uj5u.com熱心網友回復：
另一種方法是Balltree。它可以查詢最近的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))
對于p串列中的 a distances_points_tuples，p[0]是到 的距離(0,0)，p[1][0]是 x，p[1][1]是 y。
我不確定什么是“最小” x。注意我使用np.abs()x, 來定義二級排序。
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))]
轉載請註明出處，本文鏈接：https://www.uj5u.com/qiye/395976.html