Los k valores más cercanos a un objetivo
La misión
Problema
Dada una lista no ordenada de enteros nums, un target y una cantidad k, devuelve los k valores más cercanos al objetivo. Cuando dos valores están igual de lejos, el menor se considera más cercano. Devuelve los valores elegidos en orden ascendente.
Ejemplos
Input: nums = [9, 2, 14, 5, 7, 11], target = 8, k = 3
Output: [5, 7, 9]
Por qué: 7 y 9 están a 1; luego 5 y 11 empatan a 3 y gana el valor menor
Input: nums = [1, 10, 4, 4], target = 4, k = 2
Output: [4, 4]
Por qué: los valores repetidos cuentan por separado
Input: nums = [3], target = 100, k = 1
Output: [3]
Por qué: caso límite: el único valor es el más cercano, por lejos que esté
Pistas
0 / 3
Ordenar por distancia funciona en n log n. Solo necesitas k valores, así que piensa qué guardarías mientras lees la lista una sola vez.
Guarda los k valores más cercanos vistos hasta ahora, con el más lejano de ellos a mano. Un valor nuevo solo importa si está más cerca que ese más lejano.
Guarda cada valor como (distancia negada, valor negado) en un min-heap de tamaño k, para que el valor guardado más lejano, y el mayor en caso de empate, quede en la raíz. Reemplaza la raíz cada vez que una entrada nueva sea mayor que ella en la comparación y, al final, ordena los sobrevivientes.
- Tiempo objetivo
- O(n log k)
- Espacio objetivo
- O(k)
Solución
Es el problema de k puntos más cercanos, pero en una recta: la distancia es una sola diferencia absoluta, y el heap (montículo) de tamaño k guarda los k mejores candidatos con el peor en la raíz, listo para ser desalojado. Negar tanto la distancia como el valor convierte el min-heap de Python en ese max-heap e integra la regla de empate en la comparación, ya que, en un empate, el valor mayor es el peor candidato. Un valor nuevo reemplaza la raíz solo cuando su entrada es mayor, es decir, más cercana, o igual de cercana y más pequeña. El tiempo es O(n log k) y el heap usa O(k) de espacio, lo que importa cuando la lista es un stream largo y k es pequeño.
import heapq
def closest_k(nums, target, k):
heap = [] # k closest so far, the worst at the root
for x in nums:
entry = (-abs(x - target), -x) # farther, then larger, is worse
if len(heap) < k:
heapq.heappush(heap, entry)
elif entry > heap[0]: # closer than the worst kept value
heapq.heapreplace(heap, entry)
return sorted(-x for _, x in heap)
print(closest_k([9, 2, 14, 5, 7, 11], 8, 3)) # -> [5, 7, 9]
print(closest_k([1, 10, 4, 4], 4, 2)) # -> [4, 4]
print(closest_k([3], 100, 1)) # -> [3]¿Lo que te frena es la idea y no el código? K Closest Points lo explica.