K Closest Points to Origin
Tienes n puntos en un plano: el punto i es (xs[i], ys[i]). Devuelve los k puntos más cercanos al origen (0, 0), cada uno como un par [x, y].
Ordena la respuesta por distancia al origen, primero el más cercano. Si varios puntos están a la misma distancia, ordénalos primero por x menor y luego por y menor. Un punto listado más de una vez cuenta una vez por cada aparición.
Función
- xsinteger-array
- la coordenada x de cada punto
- ysinteger-array
- la coordenada y de cada punto
- kinteger
- cuántos puntos devolver
- Devuelveinteger-2d-array
- los k puntos más cercanos como pares [x, y], ordenados de más cercano a más lejano; en caso de empate, por x y luego por y
Restricciones
n == xs.length == ys.length1 ≤ k ≤ n ≤ 5000-104 ≤ xs[i], ys[i] ≤ 104- Los puntos pueden repetirse; cada copia es un punto independiente.
Ejemplos
- Entrada
- xs = [3, -1, 2, 0]ys = [1, 2, -2, 5]k = 2
- Salida
- [[-1, 2], [2, -2]]
- Explicación
- Las distancias al cuadrado son 10, 5, 8 y 25. Las dos más pequeñas corresponden a
(-1, 2)con 5 y a(2, -2)con 8, en ese orden.
- Entrada
- xs = [1, -1, 0, 1]ys = [1, 1, 2, -1]k = 3
- Salida
- [[-1, 1], [1, -1], [1, 1]]
- Explicación
(1, 1),(-1, 1)y(1, -1)tienen todos una distancia al cuadrado de 2, y(0, 2)tiene 4. Entre los puntos empatados,(-1, 1)tiene la x más pequeña, y(1, -1)va antes que(1, 1)según la y.
- Entrada
- xs = [7]ys = [-7]k = 1
- Salida
- [[7, -7]]
- Explicación
- Solo hay un punto y necesitas uno, así que la respuesta es
(7, -7).
Para ir más allá
Ahora los puntos llegan de uno en uno, y después de cada uno debes indicar los k más cercanos hasta ese momento. ¿Cuánta memoria necesitas?
Pistas
Ábrelas de una en una. Cada una revela un poco más.
Nunca necesitas la distancia real. ¿Qué puedes comparar en lugar de
√(x² + y²)y aun así obtener el mismo orden?Supón que conservas los
kpuntos más cercanos que has visto hasta ahora. ¿Con cuál de ellos compite un punto nuevo?Mantén un montículo máximo de como máximo
kpuntos ordenados por(x² + y², x, y). Reemplaza el elemento superior cuando un punto nuevo vaya antes que él y, al final, saca los puntos del montículo para completar la respuesta desde el final.
Solución
La distancia no necesita raíz cuadrada: x² + y² da el mismo orden y sigue siendo un entero. Solo necesitas k de los n puntos, así que un montículo máximo con los k más cercanos hasta el momento, con el más lejano en la cima listo para ser reemplazado, cuesta O(n log k) en lugar de una ordenación completa.
Elige el punto más cercano k veces
Correcto, pero no termina con las pruebas más grandes
Intuición
El primer punto de la respuesta es el más cercano de todos, el segundo es el más cercano de los restantes, y así sucesivamente. Así que recorre los puntos k veces, tomando cada vez el punto que aparece primero según (x² + y², x, y) entre los que aún no se han tomado.
En cada recorrido se examinan los n puntos. Para n = 5000 y k = 2500, eso supone 1.25 × 10^7 comparaciones de tres componentes.
Algoritmo
- Marca cada punto como no seleccionado.
- Repite
kveces: recorre los puntos no seleccionados y encuentra el primero según(x² + y², x, y). - Márcalo como seleccionado y añade
[x, y]a la respuesta. - Devuelve la respuesta.
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 resultOrdena cada punto
Intuición
La respuesta son los primeros k puntos del orden completo, así que ordena todos los puntos por (x² + y², x, y) y conserva los primeros k. En el ejemplo 1, las claves ordenadas son (5, -1, 2), (8, 2, -2), (10, 3, 1) y (25, 0, 5), y las dos primeras dan la respuesta.
La ordenación cuesta O(n log n), sea cual sea k. Cuando k es pequeño, la mayor parte de ese trabajo ordena puntos que nunca llegan a formar parte de la respuesta.
Algoritmo
- Construye la clave de cada punto
(x² + y², x, y). - Ordena los puntos por clave.
- Devuelve los primeros
kcomo pares[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]]Conserva los k elementos más cercanos en un montículo máximo
Intuición
Conserva los mejores k puntos vistos hasta el momento. Un punto nuevo solo puede expulsar el punto conservado que ocupa el último lugar, así que guarda los puntos conservados en un montículo máximo según (x² + y², x, y), con ese punto en la cima. Una vez que se hayan almacenado k puntos, un punto que ocupe un lugar anterior a la cima la reemplaza; cualquier otro punto se descarta, porque los k puntos almacenados ya ocupan lugares anteriores.
En el ejemplo 2, con k = 3, la cima después de los primeros tres puntos es (0, 2), con la clave (4, 0, 2). El punto (1, -1) tiene la clave (2, 1, -1), ocupa un lugar anterior y lo reemplaza.
Un montículo solo está ordenado parcialmente, así que elimina la cima k veces y llena la respuesta desde su última posición hasta la primera. Cada punto requiere como máximo un paso de montículo O(log k), por lo que el tiempo es O(n log k) y la memoria O(k).
Algoritmo
- Crea un max-heap vacío con prioridad según
(x² + y², x, y). - Inserta cada uno de los primeros
kpuntos. - Para cada punto posterior, compáralo con el primero: si tiene mayor prioridad, intercámbialo y haz que descienda por el heap; de lo contrario, sáltatelo.
- Extrae el primero
kveces; cada punto extraído ocupa la última posición libre de la respuesta. - Devuelve la respuesta.
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
Errores comunes y casos límite
- Omitir el desempate. El ejemplo 2 tiene tres puntos a distancia 2; sin comparar
xy despuésy, aparecen en el orden de entrada en lugar de(-1, 1),(1, -1),(1, 1). - Mantener un montículo mínimo de
kpuntos. Su cima es el punto más cercano, así que cada expulsión descarta un punto que la respuesta necesita, y al final quedan loskmás lejanos. - Leer la respuesta directamente del arreglo del montículo. Ese arreglo solo está parcialmente ordenado; primero, extrae los puntos uno por uno.
- Eliminar los puntos repetidos. Si
(5, 5)aparece tres veces yk = 3, la respuesta es ese punto tres veces.
Preguntas frecuentes4
¿Cuál es la complejidad temporal de K Closest Points to Origin?
Ordenar todos los puntos lleva O(n log n). La versión con heap requiere O(n log k) para el recorrido más O(k log k) para ordenar los k puntos restantes, y mantiene solo O(k) puntos en memoria.
¿Por qué usar un montículo máximo y no un montículo mínimo para los k puntos más cercanos?
Un punto nuevo compite con el más lejano de los k puntos conservados, así que ese punto debe estar en la cima. Un montículo mínimo solo funciona si contiene los n puntos para que puedas eliminar los k más cercanos, lo que cuesta O(n) de memoria en lugar de O(k).
¿Necesitas la raíz cuadrada para comparar distancias?
No. Para los números que no son negativos, a < b exactamente cuando √a < √b, así que x² + y² da el mismo orden que la distancia. También sigue siendo un entero: como máximo 2 × 10^8 aquí, dentro del rango de 32 bits.
¿Se puede resolver K Closest Points to Origin en O(n) tiempo?
En promedio, sí. Quickselect particiona los puntos alrededor de un pivote aleatorio según el mismo orden (x² + y², x, y) y continúa solo en el lado que contiene la posición k, en O(n) en promedio. Los k puntos a la izquierda de esa posición son la respuesta; ordenarlos añade O(k log k).
Problemas similares
Problemas que usan las mismas ideas. Resolver dos o tres es lo que fija un patrón.
def kClosest(xs, ys, k):
# Escribe el código aquíPrueba #1
Prueba #2
Prueba #3
Argumentos
xs = [3, -1, 2, 0] ys = [1, 2, -2, 5] k = 2
Salida Esperada
[[-1, 2], [2, -2]]