K Closest Points to Origin

Q: Wie hoch ist die Zeitkomplexität von K nächstgelegenen Punkten zum Ursprung?

Das Sortieren aller Punkte benötigt O(n log n) . Die Heap-Version benötigt für den Durchlauf O(n log k) plus O(k log k) , um die k verbleibenden Punkte zu ordnen, und hält nur O(k) Punkte im Speicher.

Q: Brauchst du die Quadratwurzel, um Entfernungen zu vergleichen?

Nein. Für Zahlen, die nicht negativ sind, gilt a < b genau dann, wenn √a < √b ; daher ergibt x² + y² dieselbe Reihenfolge wie der Abstand. Es bleibt außerdem eine ganze Zahl: hier höchstens 2 × 10^8 , also innerhalb des 32-Bit-Bereichs.

Q: Kann man K nächstgelegene Punkte zum Ursprung in O(n)-Zeit lösen?

Im Durchschnitt ja. Quickselect partitioniert die Punkte anhand derselben Reihenfolge (x² + y², x, y) um einen zufälligen Pivot und fährt nur auf der Seite fort, auf der sich Position k befindet, im Durchschnitt in O(n) . Die k Punkte links von dieser Position sind die Antwort; durch das Sortieren kommen O(k log k) hinzu.

MittelHeap Sortieren

+10

Du erhältst n Punkte auf einer Ebene: Punkt i ist (xs[i], ys[i]). Gib die k Punkte zurück, die dem Ursprung (0, 0) am nächsten liegen, jeweils als Paar [x, y].

Ordne die Antwort nach der Entfernung vom Ursprung, beginnend mit dem nächstgelegenen Punkt. Punkte mit gleicher Entfernung werden zuerst nach dem kleineren x-Wert und dann nach dem kleineren y-Wert geordnet. Ein mehrfach aufgeführter Punkt zählt für jedes Vorkommen einmal.

Funktion

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

xsinteger-array: die x-Koordinate jedes Punktes
ysinteger-array: die y-Koordinate jedes Punktes
kinteger: wie viele Punkte zurückgegeben werden
Gibt zurückinteger-2d-array: die k nächstgelegenen Punkte als [x, y]-Paare, vom nächsten zum fernsten, bei Gleichstand sortiert nach x und dann nach y

Einschränkungen

n == xs.length == ys.length
1 ≤ k ≤ n ≤ 5000
-10⁴ ≤ xs[i], ys[i] ≤ 10⁴
Punkte können sich wiederholen; jede Kopie ist ein eigener Punkt.

Beispiele

Eingabe: xs = [3, -1, 2, 0]ys = [1, 2, -2, 5]k = 2
Ausgabe: [[-1, 2], [2, -2]]
Erklärung: Die quadrierten Abstände betragen 10, 5, 8 und 25. Die beiden kleinsten gehören zu (-1, 2) mit 5 und (2, -2) mit 8, in dieser Reihenfolge.

Eingabe: xs = [1, -1, 0, 1]ys = [1, 1, 2, -1]k = 3
Ausgabe: [[-1, 1], [1, -1], [1, 1]]
Erklärung: (1, 1), (-1, 1) und (1, -1) haben alle den quadrierten Abstand 2, und (0, 2) hat 4. Unter den Punkten mit gleichem Abstand hat (-1, 1) den kleinsten x-Wert, und (1, -1) kommt nach y vor (1, 1).

Eingabe: xs = [7]ys = [-7]k = 1
Ausgabe: [[7, -7]]
Erklärung: Es gibt nur einen Punkt, und du brauchst einen, also ist die Antwort selbst (7, -7).

Weiterführende Frage

Die Punkte treffen nun einzeln ein, und nach jedem musst du die k bisher nächsten melden. Wie viel Speicher benötigst du?

Tipps

Öffne sie nacheinander. Jeder verrät ein bisschen mehr.

0 von 3 geöffnet

Lösung

Für die Distanz ist keine Quadratwurzel nötig: x² + y² ergibt dieselbe Reihenfolge und bleibt eine ganze Zahl. Du brauchst nur k der n Punkte, daher kostet ein Max-Heap mit den bisher k nächsten Punkten, bei dem der am weitesten entfernte oben liegt und ersetzt werden kann, O(n log k) statt einer vollständigen Sortierung.

Den nächstgelegenen Punkt k-mal auswählen

Korrekt, wird aber bei den größten Tests nicht fertig

Idee

Der erste Punkt der Antwort ist von allen Punkten der nächste, der zweite ist der nächste der übrigen Punkte und so weiter. Durchlaufe also die Punkte k-mal und wähle jedes Mal unter den noch nicht ausgewählten Punkten den Punkt aus, der nach (x² + y², x, y) zuerst kommt.

Bei jedem Durchlauf werden alle n Punkte berücksichtigt. Für n = 5000 und k = 2500 sind das 1.25 × 10^7 Vergleiche von Dreiergruppen.

Algorithmus

Markiere jeden Punkt als nicht genommen.
Wiederhole k-mal: Durchsuche die nicht genommenen Punkte und finde denjenigen, der nach (x² + y², x, y) zuerst kommt.
Markiere ihn als genommen und füge [x, y] zur Antwort hinzu.
Gib die Antwort zurück.

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

Sortiere jeden Punkt

Idee

Die Antwort besteht aus den ersten k Punkten der vollständigen Reihenfolge. Sortiere also jeden Punkt nach (x² + y², x, y) und behalte die ersten k. In Beispiel 1 lauten die sortierten Schlüssel (5, -1, 2), (8, 2, -2), (10, 3, 1) und (25, 0, 5), und die ersten beiden ergeben die Antwort.

Das Sortieren kostet O(n log n), unabhängig davon, wie groß k ist. Wenn k klein ist, entfällt der größte Teil dieser Arbeit auf das Sortieren von Punkten, die es nie in die Antwort schaffen.

Algorithmus

Erstelle den Schlüssel für jeden Punkt (x² + y², x, y).
Sortiere die Punkte nach Schlüssel.
Gib die ersten k davon als [x, y]-Paare zurück.

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

Behalte die k nächstgelegenen in einem Max-Heap

Idee

Behalte die bisher besten k Punkte. Ein neuer Punkt kann nur den gespeicherten Punkt verdrängen, der am schlechtesten abschneidet. Speichere die gespeicherten Punkte daher in einem Max-Heap nach (x² + y², x, y), sodass dieser Punkt oben liegt. Sobald k Punkte gespeichert sind, ersetzt ein Punkt, der weiter vorne liegt, den obersten; jeder andere Punkt wird verworfen, da die k gespeicherten Punkte bereits vor ihm liegen.

In Beispiel 2 mit k = 3 ist der oberste Punkt nach den ersten drei Punkten (0, 2) mit dem Schlüssel (4, 0, 2). Der Punkt (1, -1) hat den Schlüssel (2, 1, -1), liegt weiter vorne und ersetzt ihn.

Ein Heap ist nur teilweise sortiert. Entferne daher k Mal den obersten Punkt und fülle die Antwort vom letzten Platz bis zum ersten. Jeder Punkt benötigt höchstens einen Heap-Schritt von O(log k), daher beträgt die Laufzeit O(n log k) und der Speicherbedarf O(k).

Algorithmus

Erstelle einen leeren Max-Heap, geordnet nach (x² + y², x, y).
Füge die ersten k Punkte ein.
Vergleiche jeden späteren Punkt mit dem obersten Element: Wenn er weiter vorne rangiert, tausche ihn ein und lasse ihn nach unten durchsickern; andernfalls überspringe ihn.
Entferne das oberste Element k-mal; jeder entfernte Punkt füllt den letzten freien Platz in der Antwort.
Gib die Antwort zurück.

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

Stolperfallen und Grenzfälle

Die Gleichstandsregel überspringen. Beispiel 2 enthält drei Punkte im Abstand 2; ohne den Vergleich von x und anschließend y erscheinen sie in der Eingabereihenfolge statt als (-1, 1), (1, -1), (1, 1).
Einen Min-Heap mit k Punkten beibehalten. An seiner Spitze steht der nächstgelegene Punkt. Daher entfernt jede Löschung einen Punkt, den die Antwort benötigt, und am Ende erhältst du die k am weitesten entfernten Punkte.
Die Antwort direkt aus dem Array des Heaps auslesen. Dieses Array ist nur teilweise sortiert; entferne die Punkte zuerst einzeln.
Wiederholte Punkte entfernen. Wenn (5, 5) dreimal aufgeführt ist und k = 3 gilt, besteht die Antwort dreimal aus diesem Punkt.

Häufige Fragen4

Wie hoch ist die Zeitkomplexität von K nächstgelegenen Punkten zum Ursprung?

Das Sortieren aller Punkte benötigt O(n log n). Die Heap-Version benötigt für den Durchlauf O(n log k) plus O(k log k), um die k verbleibenden Punkte zu ordnen, und hält nur O(k) Punkte im Speicher.

Warum einen Max-Heap und keinen Min-Heap für die k nächstgelegenen Punkte verwenden?

Ein neuer Punkt konkurriert mit dem am weitesten entfernten der k beibehaltenen Punkte, daher muss dieser Punkt ganz oben liegen. Ein Min-Heap funktioniert nur, wenn er alle n Punkte enthält, sodass du die k nächsten entfernen kannst. Das benötigt O(n) statt O(k) Speicher.

Brauchst du die Quadratwurzel, um Entfernungen zu vergleichen?

Nein. Für Zahlen, die nicht negativ sind, gilt a < b genau dann, wenn √a < √b; daher ergibt x² + y² dieselbe Reihenfolge wie der Abstand. Es bleibt außerdem eine ganze Zahl: hier höchstens 2 × 10^8, also innerhalb des 32-Bit-Bereichs.

Kann man K nächstgelegene Punkte zum Ursprung in O(n)-Zeit lösen?

Im Durchschnitt ja. Quickselect partitioniert die Punkte anhand derselben Reihenfolge (x² + y², x, y) um einen zufälligen Pivot und fährt nur auf der Seite fort, auf der sich Position k befindet, im Durchschnitt in O(n). Die k Punkte links von dieser Position sind die Antwort; durch das Sortieren kommen O(k log k) hinzu.

def kClosest(xs, ys, k):
    # Schreibe hier den Code

Test #1

Test #2

Test #3

Argumente

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

Erwartete Ausgabe

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

K Closest Points to Origin

Funktion

Einschränkungen

Beispiele

Tipps

Lösung

Den nächstgelegenen Punkt k-mal auswählen

Sortiere jeden Punkt

Behalte die k nächstgelegenen in einem Max-Heap

Stolperfallen und Grenzfälle

Häufige Fragen4

Ähnliche Aufgaben