K Closest Points to Origin

Q: Qual è la complessità temporale di K Closest Points to Origin?

Ordinare tutti i punti richiede O(n log n) . La versione con heap richiede O(n log k) per la scansione, più O(k log k) per ordinare i k punti rimasti, e mantiene in memoria solo O(k) punti.

Q: Perché usare un max-heap e non un min-heap per i k punti più vicini?

Un nuovo punto compete con il più lontano tra i k punti mantenuti, quindi quel punto deve trovarsi in cima. Un min-heap funziona solo se contiene tutti gli n punti, così puoi rimuovere i k più vicini, il che richiede O(n) memoria invece di O(k) .

Q: Ti serve la radice quadrata per confrontare le distanze?

No. Per i numeri non negativi, a < b esattamente quando √a < √b , quindi x² + y² dà lo stesso ordinamento della distanza. Inoltre rimane un intero: al massimo 2 × 10^8 qui, entro l’intervallo a 32 bit.

Q: È possibile risolvere «K punti più vicini all'origine» in tempo O(n)?

In media, sì. Quickselect partiziona i punti attorno a un pivot casuale secondo lo stesso ordine (x² + y², x, y) e continua solo sul lato che contiene la posizione k , in O(n) in media. I k punti a sinistra di quella posizione sono la risposta; ordinarli aggiunge O(k log k) .

MedioHeap Ordinamento

+10

Hai n punti su un piano: il punto i è (xs[i], ys[i]). Restituisci i k punti più vicini all’origine (0, 0), ciascuno come coppia [x, y].

Ordina la risposta in base alla distanza dall’origine, dal più vicino al più lontano. I punti alla stessa distanza vanno ordinati prima per x crescente, poi per y crescente. Un punto elencato più di una volta conta una volta per ogni occorrenza.

Funzione

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

xsinteger-array: la coordinata x di ogni punto
ysinteger-array: la coordinata y di ogni punto
kinteger: quanti punti restituire
Restituisceinteger-2d-array: i k punti più vicini come coppie [x, y], dal più vicino al più lontano, a parità di distanza ordinati prima per x e poi per y

Vincoli

n == xs.length == ys.length
1 ≤ k ≤ n ≤ 5000
-10⁴ ≤ xs[i], ys[i] ≤ 10⁴
I punti possono ripetersi; ogni copia è un punto separato.

Esempi

Input: xs = [3, -1, 2, 0]ys = [1, 2, -2, 5]k = 2
Output: [[-1, 2], [2, -2]]
Spiegazione: Le distanze al quadrato sono 10, 5, 8 e 25. Le due più piccole appartengono a (-1, 2) con 5 e a (2, -2) con 8, in quest’ordine.

Input: xs = [1, -1, 0, 1]ys = [1, 1, 2, -1]k = 3
Output: [[-1, 1], [1, -1], [1, 1]]
Spiegazione: (1, 1), (-1, 1) e (1, -1) hanno tutti distanza al quadrato pari a 2, mentre (0, 2) ha distanza 4. Tra i punti a pari merito, (-1, 1) ha la x più piccola e (1, -1) precede (1, 1) in base alla y.

Input: xs = [7]ys = [-7]k = 1
Output: [[7, -7]]
Spiegazione: C’è un solo punto e te ne serve uno, quindi la risposta è proprio (7, -7).

Per approfondire

I punti arrivano ora uno alla volta e, dopo ciascuno, devi indicare i k più vicini trovati finora. Quanta memoria ti serve?

Suggerimenti

Aprili uno alla volta. Ognuno rivela un po’ di più.

0 di 3 aperti

Soluzione

La distanza non richiede la radice quadrata: x² + y² dà lo stesso ordinamento e rimane un numero intero. Ti servono solo k degli n punti, quindi un max-heap dei k punti più vicini trovati finora, con quello più lontano in cima pronto per essere sostituito, ha un costo di O(n log k) invece di un ordinamento completo.

Scegli il punto più vicino k volte

Corretto, ma non termina sui test più grandi

Intuizione

Il primo punto della risposta è il più vicino in assoluto, il secondo è il più vicino tra quelli rimanenti, e così via. Quindi esamina i punti k volte, scegliendo ogni volta il punto che viene prima secondo (x² + y², x, y) tra quelli non ancora scelti.

Ogni scansione considera tutti i punti n. Per n = 5000 e k = 2500 si tratta di 1.25 × 10^7 confronti a tre componenti.

Algoritmo

Contrassegna ogni punto come non preso.
Ripeti k volte: esamina i punti non presi e trova quello che viene per primo secondo (x² + y², x, y).
Contrassegnalo come preso e aggiungi [x, y] alla risposta.
Restituisci la risposta.

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

Ordina ogni punto

Intuizione

La risposta è costituita dai primi k punti dell’ordine completo, quindi ordina ogni punto in base a (x² + y², x, y) e conserva i primi k. Nell’esempio 1 le chiavi ordinate sono (5, -1, 2), (8, 2, -2), (10, 3, 1) e (25, 0, 5), e le prime due danno la risposta.

L’ordinamento richiede O(n log n) indipendentemente dal valore di k. Quando k è piccolo, gran parte del lavoro consiste nell’ordinare punti che non entreranno mai nella risposta.

Algoritmo

Costruisci la chiave di ogni punto (x² + y², x, y).
Ordina i punti per chiave.
Restituisci i primi k come coppie [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]]

Mantieni i k più vicini in un max-heap

Intuizione

Conserva i migliori punti k visti finora. Un nuovo punto può eliminare solo il punto conservato che si classifica ultimo, quindi memorizza i punti conservati in un max-heap basato su (x² + y², x, y), con quel punto in cima. Una volta memorizzati k punti, un punto che si classifica prima di quello in cima lo sostituisce; qualsiasi altro punto viene scartato, perché k punti memorizzati si classificano già prima di esso.

Nell’esempio 2 con k = 3, il punto in cima dopo i primi tre punti è (0, 2) con chiave (4, 0, 2). Il punto (1, -1) ha chiave (2, 1, -1), si classifica prima e lo sostituisce.

Un heap è ordinato solo parzialmente, quindi rimuovi l’elemento in cima k volte e riempi la risposta dall’ultima posizione alla prima. Ogni punto richiede al massimo un’operazione sull’heap di O(log k), quindi il tempo è O(n log k) e la memoria è O(k).

Algoritmo

Crea un max-heap vuoto con chiave (x² + y², x, y).
Inserisci ciascuno dei primi k punti.
Per ogni punto successivo, confrontalo con quello in cima: se si classifica prima, sostituiscilo e fallo scendere; altrimenti, ignoralo.
Rimuovi l'elemento in cima k volte; ogni punto rimosso riempie l'ultimo slot libero della risposta.
Restituisci la risposta.

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

Trappole e casi limite

Saltare lo spareggio. L'esempio 2 ha tre punti a distanza 2; senza confrontare x e poi y, risultano nell'ordine di input invece che come (-1, 1), (1, -1), (1, 1).
Mantenere un heap minimo di k punti. La sua cima è il punto più vicino, quindi ogni rimozione elimina un punto necessario nella risposta e alla fine restano i k punti più lontani.
Leggere la risposta direttamente dall'array dell'heap. L'array è ordinato solo in parte; rimuovi prima i punti uno per uno.
Rimuovere i punti ripetuti. Se (5, 5) compare tre volte e k = 3, la risposta è quel punto tre volte.

Domande frequenti4

Qual è la complessità temporale di K Closest Points to Origin?

Ordinare tutti i punti richiede O(n log n). La versione con heap richiede O(n log k) per la scansione, più O(k log k) per ordinare i k punti rimasti, e mantiene in memoria solo O(k) punti.

Perché usare un max-heap e non un min-heap per i k punti più vicini?

Un nuovo punto compete con il più lontano tra i k punti mantenuti, quindi quel punto deve trovarsi in cima. Un min-heap funziona solo se contiene tutti gli n punti, così puoi rimuovere i k più vicini, il che richiede O(n) memoria invece di O(k).

Ti serve la radice quadrata per confrontare le distanze?

No. Per i numeri non negativi, a < b esattamente quando √a < √b, quindi x² + y² dà lo stesso ordinamento della distanza. Inoltre rimane un intero: al massimo 2 × 10^8 qui, entro l’intervallo a 32 bit.

È possibile risolvere «K punti più vicini all'origine» in tempo O(n)?

In media, sì. Quickselect partiziona i punti attorno a un pivot casuale secondo lo stesso ordine (x² + y², x, y) e continua solo sul lato che contiene la posizione k, in O(n) in media. I k punti a sinistra di quella posizione sono la risposta; ordinarli aggiunge O(k log k).

def kClosest(xs, ys, k):
    # Scrivi il codice qui

Test #1

Test #2

Test #3

Argomenti

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

Output atteso

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

K Closest Points to Origin

Funzione

Vincoli

Esempi

Suggerimenti

Soluzione

Scegli il punto più vicino k volte

Ordina ogni punto

Mantieni i k più vicini in un max-heap

Trappole e casi limite

Domande frequenti4

Problemi simili