K Closest Points to Origin
Düzlemde n noktanız var: i. nokta (xs[i], ys[i]) şeklindedir. Orijine (0, 0) en yakın k noktayı, her birini [x, y] çifti olarak döndürün.
Yanıtı orijine olan uzaklığa göre, en yakından başlayarak sıralayın. Aynı uzaklıktaki noktalar önce daha küçük x değerine, ardından daha küçük y değerine göre sıralanır. Bir nokta birden fazla kez listelenmişse, her kopya bir kez sayılır.
Fonksiyon
- xsinteger-array
- x koordinatı her noktanın
- ysinteger-array
- her noktanın y koordinatı
- kinteger
- kaç puan döndürülmeli
- Döndürürinteger-2d-array
- En yakından başlayarak, eşitliklerde önce x, sonra y değerine göre sıralanmış [x, y] çiftleri olarak k en yakın nokta
Kısıtlar
n == xs.length == ys.length1 ≤ k ≤ n ≤ 5000-104 ≤ xs[i], ys[i] ≤ 104- Noktalar tekrarlanabilir; her kopya ayrı bir noktadır.
Örnekler
- Girdi
- xs = [3, -1, 2, 0]ys = [1, 2, -2, 5]k = 2
- Çıktı
- [[-1, 2], [2, -2]]
- Açıklama
- Kareleri alınmış uzaklıklar 10, 5, 8 ve 25'tir. En küçük iki değer, sırasıyla 5 ile
(-1, 2)noktasına ve 8 ile(2, -2)noktasına aittir.
- Girdi
- xs = [1, -1, 0, 1]ys = [1, 1, 2, -1]k = 3
- Çıktı
- [[-1, 1], [1, -1], [1, 1]]
- Açıklama
(1, 1),(-1, 1)ve(1, -1)noktalarının tümünün kareli uzaklığı 2'dir;(0, 2)noktasınınki ise 4'tür. Eşit uzaklıktaki noktalar arasında(-1, 1)en küçük x değerine sahiptir ve(1, -1), y değerine göre(1, 1)'den önce gelir.
- Girdi
- xs = [7]ys = [-7]k = 1
- Çıktı
- [[7, -7]]
- Açıklama
- Yalnızca bir nokta var ve bir noktaya ihtiyacınız olduğundan cevap
(7, -7)olur.
Ek soru
Noktalar artık teker teker geliyor ve her birinden sonra, şimdiye kadar gelenler arasından en yakın k noktayı bildirmelisiniz. Ne kadar belleğe ihtiyacınız var?
İpuçları
Tek tek açın. Her biri biraz daha fazlasını gösterir.
Gerçek uzaklığa hiçbir zaman ihtiyacın yok.
√(x² + y²)yerine neyi karşılaştırabilir ve yine de aynı sıralamayı elde edebilirsin?Diyelim ki şu ana kadar görülen en yakın
knoktayı tutuyorsun. Yeni bir nokta bunlardan hangisiyle rekabet eder?knoktadan oluşan,(x² + y², x, y)sıralamasına göre düzenlenmiş en fazlaknoktalı bir max-heap tut. Yeni bir nokta en üsttekinden önce geliyorsa en üsttekini onunla değiştir ve sonunda yanıtı sondan doldurmak için noktaları heap'ten çıkar.
Çözüm
Uzaklık için karekök gerekmez: x² + y² aynı sıralamayı verir ve tam sayı olarak kalır. n noktanın yalnızca k tanesine ihtiyacınız var; bu nedenle şimdiye kadarki en yakın k noktayı tutan ve en uzaktaki noktayı değiştirmeye hazır biçimde en üstte bulunduran bir max-heap, tam sıralama yerine O(n log k) maliyetlidir.
En yakın noktayı k kez seç
Doğru, ama en büyük testlerde bitmiyor
Sezgi
Cevabın ilk noktası hepsinin en yakınıdır, ikinci nokta geri kalanların en yakınıdır ve bu böyle devam eder. Bu yüzden noktaları k kez tara ve her seferinde henüz alınmamış noktalar arasından (x² + y², x, y) bakımından ilk gelen noktayı seç.
Her tarama n noktanın tümüne dokunur. n = 5000 ve k = 2500 için bu, 1.25 × 10^7 üç parçalı karşılaştırma demektir.
Algoritma
- Her noktayı alınmamış olarak işaretle.
kkez tekrarla: alınmamış noktaları tara ve(x² + y², x, y)sıralamasında ilk geleni bul.- Noktayı alınmış olarak işaretle ve yanıta
[x, y]ekle. - Yanıtı döndür.
def kClosest(xs, ys, k):
n = len(xs)
taken = [False] * n
result = []
for _ in range(k):
best = -1
for i in range(n):
# Compare (squared distance, x, y): the order the answer uses.
if not taken[i] and (best == -1 or
(xs[i] * xs[i] + ys[i] * ys[i], xs[i], ys[i]) <
(xs[best] * xs[best] + ys[best] * ys[best], xs[best], ys[best])):
best = i
taken[best] = True
result.append([xs[best], ys[best]])
return resultHer noktayı sırala
Sezgi
Yanıt, tam sıralamanın ilk k noktasıdır; bu nedenle tüm noktaları (x² + y², x, y) değerine göre sırala ve ilk k tanesini al. 1. örnekte sıralanmış anahtarlar (5, -1, 2), (8, 2, -2), (10, 3, 1) ve (25, 0, 5) olur ve ilk ikisi yanıtı verir.
Sıralamanın maliyeti, k ne olursa olsun O(n log n) olur. k küçük olduğunda, bu işin çoğu yanıta hiçbir zaman girmeyen noktaları sıralamak için harcanır.
Algoritma
- Her noktanın anahtarını oluştur:
(x² + y², x, y). - Noktaları anahtara göre sırala.
- İlk
ktanesini[x, y]çiftleri olarak döndür.
def kClosest(xs, ys, k):
points = list(zip(xs, ys))
# Sort by squared distance, then x, then y: the order the answer uses.
points.sort(key=lambda p: (p[0] * p[0] + p[1] * p[1], p[0], p[1]))
return [[x, y] for x, y in points[:k]]En yakın k öğeyi bir maksimum yığında tutun
Sezgi
Şimdiye kadar görülen en iyi k noktayı tut. Yeni gelen bir nokta yalnızca tutulan ve sıralamada son sırada olan noktanın yerini alabilir; bu yüzden tutulan noktaları, en üstte bu nokta olacak şekilde (x² + y², x, y) anahtarına göre bir max-heap içinde sakla. k nokta saklandıktan sonra, en üsttekinden daha üst sırada yer alan bir nokta onun yerine geçer; diğer noktalar atılır, çünkü saklanan k nokta zaten onlardan daha üst sıradadır.
k = 3 olan 2. örnekte, ilk üç noktadan sonra en üstte (0, 2) bulunur ve anahtarı (4, 0, 2) olur. (1, -1) noktasının anahtarı (2, 1, -1) olur, daha üst sırada yer alır ve onun yerine geçer.
Heap yalnızca kısmen sıralıdır; bu yüzden en üstteki öğeyi k kez çıkar ve yanıtı son konumundan ilk konumuna doğru doldur. Her nokta en fazla bir O(log k) heap adımına mal olur; dolayısıyla zaman karmaşıklığı O(n log k), bellek kullanımı ise O(k) olur.
Algoritma
(x² + y², x, y)anahtarına göre sıralanan boş bir max-heap oluştur.- İlk
knoktayı ekle. - Daha sonraki her nokta için onu en üstteki noktayla karşılaştır: daha önde sıralanıyorsa onu yer değiştirip aşağı doğru düzenle; aksi hâlde atla.
- En üstteki öğeyi
kkez çıkar; çıkarılan her nokta, yanıttaki son boş yeri doldurur. - Yanıtı döndür.
import heapq
def kClosest(xs, ys, k):
# heapq is a min-heap; negating every part of (distance, x, y) puts the
# farthest kept point, in the answer's order, on top.
heap = []
for x, y in zip(xs, ys):
item = (-(x * x + y * y), -x, -y)
if len(heap) < k:
heapq.heappush(heap, item)
elif item > heap[0]:
# The new point comes before the farthest kept one: swap them.
heapq.heapreplace(heap, item)
# Popping gives the farthest first, so fill the answer from the back.
result = [None] * len(heap)
for i in range(len(result) - 1, -1, -1):
_, x, y = heapq.heappop(heap)
result[i] = [-x, -y]
return result
Tuzaklar ve uç durumlar
- Eşitlik bozma adımını atlamak. Örnek 2'de uzaklığı 2 olan üç nokta var;
xve ardındanykarşılaştırılmadığında, noktalar(-1, 1),(1, -1),(1, 1)sırası yerine giriş sırasına göre gelir. knoktalı bir min-heap tutmak. Heap'in tepesi en yakın noktadır; bu yüzden her çıkarma, cevabın ihtiyaç duyduğu bir noktayı atar ve sonunda en uzakknokta elinizde kalır.- Cevabı doğrudan heap'in dizisinden okumak. Bu dizi yalnızca kısmen sıralıdır; önce noktaları teker teker çıkarın.
- Tekrarlanan noktaları kaldırmak.
(5, 5)üç kez listelenmişse vek = 3ise cevap, bu noktadan üç tanesidir.
Sıkça sorulan sorular4
K Orijine En Yakın Nokta probleminin zaman karmaşıklığı nedir?
Tüm noktaları sıralamak O(n log n) sürer. Yığın sürümü, tarama için O(n log k) ve hayatta kalan k noktayı sıralamak için O(k log k) sürer ve bellekte yalnızca O(k) nokta tutar.
k en yakın nokta için neden min-heap değil de max-heap kullanılır?
Yeni bir nokta, elde tutulan k nokta arasındaki en uzaktaki noktayla karşılaştırılır; bu nedenle o nokta en üstte olmalıdır. Bir min-yığın, yalnızca tüm n noktayı tutuyorsa işe yarar; böylece en yakın k noktayı kaldırabilirsiniz. Bu da O(k) yerine O(n) bellek kullanır.
Mesafeleri karşılaştırmak için karekök gerekiyor mu?
Hayır. Negatif olmayan sayılar için a < b tam olarak √a < √b olduğunda geçerlidir; dolayısıyla x² + y², uzaklıkla aynı sıralamayı verir. Ayrıca bir tam sayı olarak kalır: burada en fazla 2 × 10^8, yani 32 bitlik aralığın içindedir.
Orijine En Yakın K Nokta problemi O(n) zamanda çözülebilir mi?
Ortalama olarak, evet. Quickselect, noktaları rastgele bir pivotun etrafında aynı (x² + y², x, y) sıralamasına göre bölümlere ayırır ve yalnızca k konumunu içeren tarafta devam ederek bunu ortalama O(n) zamanda yapar. Bu konumun solunda kalan k nokta cevaptır; bunları sıralamak O(k log k) ek maliyet getirir.
Benzer problemler
Aynı fikirleri kullanan problemler. İki üçünü çözmek bir kalıbı kalıcı hale getirir.
def kClosest(xs, ys, k):
# Kodu buraya yazınTest #1
Test #2
Test #3
Argümanlar
xs = [3, -1, 2, 0] ys = [1, 2, -2, 5] k = 2
Beklenen Çıktı
[[-1, 2], [2, -2]]