K Closest Points to Origin

Q: Apa kompleksitas waktu K Closest Points to Origin?

Mengurutkan semua titik membutuhkan O(n log n) . Versi heap membutuhkan O(n log k) untuk pemindaian, ditambah O(k log k) untuk mengurutkan k titik yang tersisa, dan hanya menyimpan O(k) titik di memori.

Q: Mengapa menggunakan max-heap, bukan min-heap, untuk k titik terdekat?

Titik baru bersaing dengan titik terjauh dari k titik yang disimpan, jadi titik itu harus berada di posisi teratas. Min-heap hanya berfungsi jika menampung semua n titik agar kamu bisa menghapus k titik terdekat, yang membutuhkan memori O(n) alih-alih O(k) .

Q: Apakah kamu memerlukan akar kuadrat untuk membandingkan jarak?

Tidak. Untuk bilangan yang tidak negatif, a < b tepat ketika √a < √b , jadi x² + y² menghasilkan urutan yang sama dengan jarak. Hasilnya juga tetap bilangan bulat: paling banyak 2 × 10^8 di sini, masih dalam rentang 32-bit.

Q: Apakah K Titik Terdekat ke Titik Asal dapat diselesaikan dalam waktu O(n)?

Secara rata-rata, ya. Quickselect membagi titik-titik di sekitar pivot acak dengan urutan (x² + y², x, y) yang sama, lalu hanya melanjutkan pada sisi yang memuat posisi k , dengan kompleksitas rata-rata O(n) . k titik di sebelah kiri posisi itu adalah jawabannya; mengurutkannya menambahkan O(k log k) .

SedangHeap Pengurutan

+10

Kamu mendapatkan n titik pada bidang: titik i adalah (xs[i], ys[i]). Kembalikan k titik yang paling dekat dengan titik asal (0, 0), masing-masing sebagai pasangan [x, y].

Urutkan jawaban berdasarkan jarak dari titik asal, mulai dari yang terdekat. Untuk titik dengan jarak yang sama, dahulukan titik dengan x yang lebih kecil, lalu titik dengan y yang lebih kecil. Titik yang tercantum lebih dari sekali dihitung satu kali untuk setiap salinannya.

Fungsi

kClosest(xs: integer-array, ys: integer-array, k: integer) → integer-2d-array

xsinteger-array: koordinat x dari setiap titik
ysinteger-array: koordinat y setiap titik
kinteger: berapa banyak poin yang harus dikembalikan
Mengembalikaninteger-2d-array: k titik terdekat dalam bentuk pasangan [x, y], diurutkan dari yang paling dekat, jika jaraknya sama urutkan berdasarkan x lalu y

Batasan

n == xs.length == ys.length
1 ≤ k ≤ n ≤ 5000
-10⁴ ≤ xs[i], ys[i] ≤ 10⁴
Poin dapat berulang; setiap salinannya merupakan poin terpisah.

Contoh

Input: xs = [3, -1, 2, 0]ys = [1, 2, -2, 5]k = 2
Output: [[-1, 2], [2, -2]]
Penjelasan: Jarak kuadratnya adalah 10, 5, 8, dan 25. Dua jarak terkecil adalah milik (-1, 2) dengan nilai 5 dan (2, -2) dengan nilai 8, dalam urutan tersebut.

Input: xs = [1, -1, 0, 1]ys = [1, 1, 2, -1]k = 3
Output: [[-1, 1], [1, -1], [1, 1]]
Penjelasan: (1, 1), (-1, 1), dan (1, -1) semuanya memiliki jarak kuadrat 2, sedangkan (0, 2) memiliki 4. Di antara titik-titik yang seri, (-1, 1) memiliki x terkecil, dan (1, -1) berada sebelum (1, 1) berdasarkan y.

Input: xs = [7]ys = [-7]k = 1
Output: [[7, -7]]
Penjelasan: Hanya ada satu titik dan kamu membutuhkan satu titik, jadi jawabannya adalah (7, -7) itu sendiri.

Pertanyaan lanjutan

Titik-titik kini datang satu per satu, dan setelah setiap titik kamu harus melaporkan k titik terdekat sejauh ini. Berapa banyak memori yang kamu butuhkan?

Petunjuk

Buka satu per satu. Setiap petunjuk mengungkap sedikit lebih banyak.

0 dari 3 dibuka

Solusi

Jarak tidak memerlukan akar kuadrat: x² + y² memberikan urutan yang sama dan tetap berupa bilangan bulat. Kamu hanya memerlukan k dari n titik, jadi max-heap yang berisi k titik terdekat sejauh ini, dengan titik terjauh di posisi teratas agar siap diganti, membutuhkan biaya O(n log k) alih-alih mengurutkan semuanya.

Pilih titik terdekat sebanyak k kali

Benar, tetapi tidak selesai pada tes terbesar

Intuisi

Titik pertama pada jawaban adalah yang paling dekat dari semuanya, titik kedua adalah yang paling dekat di antara sisanya, dan seterusnya. Jadi, pindai titik-titik sebanyak k kali, setiap kali mengambil titik yang paling awal menurut (x² + y², x, y) di antara titik-titik yang belum diambil.

Setiap pemindaian menyentuh semua n titik. Untuk n = 5000 dan k = 2500, jumlahnya adalah 1.25 × 10^7 perbandingan tiga bagian.

Algoritma

Tandai setiap titik sebagai belum diambil.
Ulangi sebanyak k kali: pindai titik yang belum diambil dan temukan titik yang paling awal menurut (x² + y², x, y).
Tandai titik tersebut sebagai sudah diambil dan tambahkan [x, y] ke jawaban.
Kembalikan jawaban.

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 result

Urutkan setiap poin

Intuisi

Jawabannya adalah k titik pertama dari urutan lengkap, jadi urutkan setiap titik berdasarkan (x² + y², x, y) dan ambil k titik pertama. Pada contoh 1, kunci yang sudah diurutkan adalah (5, -1, 2), (8, 2, -2), (10, 3, 1), dan (25, 0, 5), dan dua yang pertama memberikan jawabannya.

Pengurutan membutuhkan biaya O(n log n), berapa pun nilai k. Saat k kecil, sebagian besar pekerjaan itu digunakan untuk mengurutkan titik-titik yang tidak pernah masuk ke dalam jawaban.

Algoritma

Buat key untuk setiap titik (x² + y², x, y).
Urutkan titik berdasarkan key.
Kembalikan k titik pertama sebagai pasangan [x, y].

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]]

Simpan k elemen terdekat dalam max-heap

Intuisi

Pertahankan k titik terbaik yang ditemukan sejauh ini. Titik baru hanya dapat menyingkirkan titik tersimpan yang berada di peringkat terakhir, jadi simpan titik-titik tersebut dalam max-heap berdasarkan (x² + y², x, y), dengan titik itu berada di puncak. Setelah k titik tersimpan, titik yang peringkatnya lebih baik daripada titik di puncak akan menggantikannya; titik lainnya dibuang karena sudah ada k titik tersimpan yang peringkatnya lebih baik.

Pada contoh 2 dengan k = 3, titik di puncak setelah tiga titik pertama adalah (0, 2) dengan kunci (4, 0, 2). Titik (1, -1) memiliki kunci (2, 1, -1), peringkatnya lebih baik, dan menggantikannya.

Heap hanya terurut sebagian, jadi keluarkan titik di puncak sebanyak k kali dan isi jawaban dari slot terakhir hingga slot pertama. Setiap titik memerlukan paling banyak satu langkah heap O(log k), sehingga waktunya O(n log k) dan memorinya O(k).

Algoritma

Buat max-heap kosong dengan kunci (x² + y², x, y).
Masukkan setiap titik dari k titik pertama.
Untuk setiap titik berikutnya, bandingkan dengan elemen teratas: jika peringkatnya lebih tinggi, tukar posisinya lalu geser ke bawah; jika tidak, lewati.
Hapus elemen teratas sebanyak k kali; setiap titik yang dihapus mengisi slot kosong terakhir pada jawaban.
Kembalikan jawaban.

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

Jebakan dan kasus tepi

Melewatkan penentuan urutan jika jaraknya sama. Contoh 2 memiliki tiga titik dengan jarak 2. Tanpa membandingkan x lalu y, titik-titik tersebut tetap dalam urutan input, bukan (-1, 1), (1, -1), (1, 1).
Menyimpan k titik dalam min-heap. Elemen teratasnya adalah titik terdekat, jadi setiap penghapusan membuang titik yang dibutuhkan oleh jawaban, dan hasil akhirnya adalah k titik terjauh.
Membaca jawaban langsung dari array heap. Array tersebut hanya terurut sebagian. Keluarkan titik-titiknya satu per satu terlebih dahulu.
Menghapus titik yang berulang. Jika (5, 5) tercantum tiga kali dan k = 3, jawabannya adalah titik tersebut sebanyak tiga kali.

Pertanyaan yang sering diajukan4

Apa kompleksitas waktu K Closest Points to Origin?

Mengurutkan semua titik membutuhkan O(n log n). Versi heap membutuhkan O(n log k) untuk pemindaian, ditambah O(k log k) untuk mengurutkan k titik yang tersisa, dan hanya menyimpan O(k) titik di memori.

Mengapa menggunakan max-heap, bukan min-heap, untuk k titik terdekat?

Titik baru bersaing dengan titik terjauh dari k titik yang disimpan, jadi titik itu harus berada di posisi teratas. Min-heap hanya berfungsi jika menampung semua n titik agar kamu bisa menghapus k titik terdekat, yang membutuhkan memori O(n) alih-alih O(k).

Apakah kamu memerlukan akar kuadrat untuk membandingkan jarak?

Tidak. Untuk bilangan yang tidak negatif, a < b tepat ketika √a < √b, jadi x² + y² menghasilkan urutan yang sama dengan jarak. Hasilnya juga tetap bilangan bulat: paling banyak 2 × 10^8 di sini, masih dalam rentang 32-bit.

Apakah K Titik Terdekat ke Titik Asal dapat diselesaikan dalam waktu O(n)?

Secara rata-rata, ya. Quickselect membagi titik-titik di sekitar pivot acak dengan urutan (x² + y², x, y) yang sama, lalu hanya melanjutkan pada sisi yang memuat posisi k, dengan kompleksitas rata-rata O(n). k titik di sebelah kiri posisi itu adalah jawabannya; mengurutkannya menambahkan O(k log k).

def kClosest(xs, ys, k):
    # Tulis kodemu di sini

Tes #1

Tes #2

Tes #3

Argumen

xs = [3, -1, 2, 0]
ys = [1, 2, -2, 5]
k = 2

Output yang diharapkan

[[-1, 2], [2, -2]]

K Closest Points to Origin

Fungsi

Batasan

Contoh

Petunjuk

Solusi

Pilih titik terdekat sebanyak k kali

Urutkan setiap poin

Simpan k elemen terdekat dalam max-heap

Jebakan dan kasus tepi

Pertanyaan yang sering diajukan4

Soal serupa