Top K Frequent Elements
Recibes un arreglo de enteros nums y un entero k. Devuelve los k valores que aparecen con mayor frecuencia en nums, ordenados de mayor a menor frecuencia. Cuando dos valores aparecen el mismo número de veces, el menor va primero.
Cada valor aparece una vez en la respuesta, independientemente de cuántas veces aparezca en nums, y k nunca es mayor que el número de valores distintos.
Función
- numsinteger-array
- los valores que se deben contar
- kinteger
- cuántos valores devolver
- Devuelveinteger-array
- los k valores más frecuentes, primero el más frecuente; en caso de empate, primero el valor más pequeño
Restricciones
1 ≤ nums.length ≤ 104-104 ≤ nums[i] ≤ 1041 ≤ k, ykes como máximo el número de valores distintos ennums.
Ejemplos
- Entrada
- nums = [4, 1, 4, 2, 1, 4, 3, 1, 4]k = 2
- Salida
- [4, 1]
- Explicación
4aparece cuatro veces,1tres veces, y2y3una vez cada uno. Los dos valores más frecuentes son4y después1.
- Entrada
- nums = [5, -2, 7, -2, 7, 5, 9]k = 2
- Salida
- [-2, 5]
- Explicación
-2,5y7aparecen dos veces cada uno y9una vez. Tres valores empatan en el primer puesto, así que los dos más pequeños,-2y5, son la respuesta.
- Entrada
- nums = [8]k = 1
- Salida
- [8]
- Explicación
- Hay un valor, así que es el más frecuente.
+16 pruebas ocultas al enviar
Pistas
Ábrelas de una en una. Cada una revela un poco más.
Empieza averiguando con qué frecuencia aparece cada valor. ¿Qué estructura de datos asigna a cada valor su cantidad en una sola pasada?
Con los recuentos a mano, quieres los
kmejores valores según un orden: primero el recuento más alto y, en caso de empate, el valor más pequeño. Ordenar todos los valores distintos funciona. Un montículo mínimo de tamañokconserva solo los valores que todavía pueden formar parte de la respuesta.Un conteo es un número entero del 1 al
n. Crea un cubo por cada conteo; el cuboccontiene los valores que aparecen exactamentecveces, y lee los cubos desde el conteo más alto hasta el más bajo. Llena los cubos recorriendo los valores de menor a mayor, y cada cubo ya queda ordenado para resolver los empates.
Solución
El recuento es la parte rápida: una sola pasada con un mapa hash obtiene el recuento de cada valor. La verdadera pregunta es cómo elegir los k mejores valores sin hacer más trabajo del necesario. Ordenar los d valores distintos por recuento cuesta O(d log d); un montículo mínimo de tamaño k reduce ese coste a O(d log k) y, como un recuento es un número entero entre 1 y n, una ordenación por cubetas ordena los valores por recuento sin hacer ninguna comparación.
Cuenta y, después, ordena por cantidad
Intuición
Primero, cuenta. Una pasada con un mapa hash de valor a cantidad convierte [4, 1, 4, 2, 1, 4, 3, 1, 4] en 4 → 4, 1 → 3, 2 → 1, 3 → 1.
Después, coloca los valores distintos en el orden de la respuesta: primero el de mayor cantidad y, si las cantidades son iguales, primero el valor menor. Ordena usando exactamente esa comparación, con la cantidad como primera clave y el valor como segunda; las primeras k entradas de la lista ordenada son la respuesta. Aquí el orden es 4, 1, 2, 3, y k = 2 conserva 4 y 1.
Contar cuesta O(n). Ordenar los d valores distintos cuesta O(d log d), como máximo O(n log n) cuando todos los valores son diferentes: 10^4 valores requieren alrededor de 1.3 × 10^5 comparaciones, lo cual es rápido. El desperdicio está en que la ordenación organiza todos los valores cuando solo importan los primeros k.
Algoritmo
- Cuenta cada valor en un mapa hash.
- Coloca los valores distintos en una lista.
- Ordena la lista por cantidad, de mayor a menor, y por valor, de menor a mayor cuando las cantidades sean iguales.
- Devuelve los primeros
kvalores.
from collections import Counter
def topKFrequent(nums, k):
counts = Counter(nums)
# Most frequent first; equal counts put the smaller value first.
ordered = sorted(counts, key=lambda value: (-counts[value], value))
return ordered[:k]Conserva los k mejores en un montículo mínimo
Intuición
Solo necesitas los k mejores valores, así que conserva solo k candidatos. Para cada valor nuevo, la pregunta es si supera al candidato más débil que conservas, donde más débil significa que tiene un recuento menor, o el mismo recuento y un valor mayor. Un montículo mínimo ordenado según esa regla mantiene arriba al candidato más débil, donde puedes leerlo en O(1) y reemplazarlo en O(log k).
Recorre los valores distintos. Mientras el montículo contenga menos de k valores, añade el valor. Después, si un valor supera al de la cima, lo reemplaza; si no, se descarta, porque ya se conservan k valores mejores. Con un montículo de biblioteca, es más corto insertar todos los valores y extraer uno cada vez que el montículo supera los k elementos, lo que conserva los mismos k valores.
Al final, el montículo contiene la respuesta, pero no en el orden de la respuesta: un montículo solo está parcialmente ordenado. Extraer elementos devuelve primero el valor más débil, así que escribe la respuesta desde la última posición hasta la primera.
Cada uno de los d valores distintos requiere como máximo una operación del montículo con k elementos, así que la selección toma O(d log k). Esto es más rápido que ordenar cuando k es mucho menor que d, como al buscar los 10 valores principales entre 8000 valores distintos.
Algoritmo
- Cuenta cada valor en un mapa hash.
- Para cada valor distinto, insértalo mientras el montículo contenga menos de
kvalores. - Cuando el montículo esté lleno, compara el valor con el de la cima, el valor más débil que se conserva. Si el nuevo valor es más fuerte, colócalo en la cima y restáuralo hacia abajo.
- Extrae elementos del montículo
kveces y escribe cada valor en la respuesta, desde la última posición hasta la primera.
import heapq
from collections import Counter
def topKFrequent(nums, k):
counts = Counter(nums)
# Entries are (count, -value). heapq keeps the smallest entry on top, which is
# the weakest value kept: the lowest count, and on a tie the larger value.
heap = []
for value, count in counts.items():
heapq.heappush(heap, (count, -value))
if len(heap) > k:
heapq.heappop(heap)
# Pops come out weakest first, so fill the answer from the back.
result = [0] * k
for i in range(k - 1, -1, -1):
result[i] = -heapq.heappop(heap)[1]
return resultContar y después ordenar en cubetas según el conteo
Intuición
Un recuento no es cualquier número: es un número entero entre 1 y n. Eso permite usar un ordenamiento por cubetas. Crea una cubeta por cada recuento; la cubeta c contiene los valores que aparecen exactamente c veces. Luego recorre las cubetas desde la n hasta la primera. Los valores salen primero en orden de mayor frecuencia, y nunca se comparan dos recuentos.
La regla para los empates pide una cosa más: dentro de una cubeta, el valor menor debe ir primero. Los valores están entre -10^4 y 10^4, así que un arreglo de R = 2 × 10^4 + 1 contadores sirve para hacer el recuento, con el valor v en el índice v + 10^4. Recorre ese arreglo del valor menor al mayor y agrega cada valor a la cubeta correspondiente a su recuento. Cada cubeta se llena en orden ascendente, que es el orden de los empates, así que nunca hace falta ordenar.
Para [5, -2, 7, -2, 7, 5, 9], el recorrido coloca -2, 5 y 7 en la cubeta 2, en ese orden, y 9 en la cubeta 1. Al recorrer las cubetas desde la 7 hacia abajo, la primera que contiene valores es la cubeta 2, y k = 2 toma -2 y 5.
El trabajo consiste en un recorrido de nums, uno de los R contadores y uno de las cubetas, O(n + R) en total: lineal para un rango fijo de valores. Si usas un mapa hash en lugar del arreglo de recuento, el recuento sigue siendo lineal, pero las cubetas se llenan en el orden del mapa y tendrías que ordenar cada una para respetar la regla de los empates.
Algoritmo
- Cuenta cada valor en un array indexado por
value + 10^4. - Crea los buckets del 1 al
n, una lista por cada recuento posible. - Recorre el array de recuento desde el valor más pequeño hasta el más grande y añade cada valor que aparezca al bucket de su recuento.
- Lee los buckets desde el recuento
nhasta el 1 y toma valores hasta tenerk.
def topKFrequent(nums, k):
OFFSET = 10000 # values run from -10^4 to 10^4
counts = [0] * (2 * OFFSET + 1)
for x in nums:
counts[x + OFFSET] += 1
# buckets[c] lists the values that occur exactly c times. Walking the
# values from smallest to largest fills every bucket in ascending order.
buckets = [[] for _ in range(len(nums) + 1)]
for i, c in enumerate(counts):
if c > 0:
buckets[c].append(i - OFFSET)
# Read the buckets from the highest count down until k values are taken.
result = []
for c in range(len(nums), 0, -1):
for value in buckets[c]:
result.append(value)
if len(result) == k:
return result
return result
Errores comunes y casos límite
El conteo rara vez está mal. El orden de la respuesta sí.
- Desempatar según el orden de aparición o el orden del mapa hash. En el segundo ejemplo,
-2,5y7aparecen dos veces, y solo la regla del valor más pequeño hace que[-2, 5]sea la respuesta correcta. - Devolver el arreglo del heap tal como está. Un heap solo está ordenado parcialmente, y su elemento superior es el valor más débil, el que debe ir al final.
- Invertir la regla de desempate del heap. De dos valores con el mismo conteo, el más grande es el más débil, así que un min-heap sobre
(count, value)expulsa el incorrecto. Usa(count, -value)o una comparación escrita para esta regla. - Crear solo tantos buckets como valores distintos haya. Un valor puede aparecer
nveces, como en[3, 3, 3, 3], así que debe existir el bucketn. - En Java, comparar dos conteos
Integercon!=. Eso compara referencias y falla cuando los conteos superan 127. Primero conviértelos aint. - Tomar un bucket entero al final. Detente en cuanto tengas
kvalores, aunque sea a mitad de un bucket.
Preguntas frecuentes4
¿Cuál es la complejidad temporal de Top K Frequent Elements?
El conteo cuesta O(n). Elegir los k primeros después cuesta O(d log d) al ordenar los d valores distintos, O(d log k) con un montículo mínimo de tamaño k, y O(n) más una pasada por el rango de valores con ordenamiento por cubetas. Como d puede llegar a n, ordenar cuesta O(n log n) en el peor de los casos y el ordenamiento por cubetas es lineal.
¿Se puede resolver Top K Frequent Elements en tiempo O(n)?
Sí, con el ordenamiento por cubetas. Los conteos son números enteros del 1 al n, así que cada valor va a la cubeta correspondiente a su conteo, y leer las cubetas desde el conteo más alto hasta el más bajo enumera los valores por frecuencia sin ningún ordenamiento por comparación. Quickselect sobre los conteos también es O(n) en promedio, pero su peor caso es cuadrático.
¿Por qué usar un montículo mínimo y no un montículo máximo?
También funciona un montículo máximo con todos los valores d: constrúyelo en O(d) y extrae elementos k veces; en total, O(d + k log d). Un montículo mínimo de tamaño k contiene solo k elementos y es adecuado para valores que llegan uno a la vez, porque su cima es el candidato a descartar. El precio es que devuelve la respuesta en orden inverso, así que rellenas el resultado desde el final.
¿Cómo se resuelven los empates en los K elementos más frecuentes?
Elige una regla y aplícala en todas partes; aquí, si las cantidades son iguales, se coloca primero el valor menor, lo que hace que la respuesta sea única. En una ordenación, compara las cantidades y después los valores. En un montículo, de dos cantidades iguales, el valor mayor es el más débil. En una ordenación por cubetas, llena las cubetas en orden ascendente de valor, y cada cubeta ya está ordenada para resolver los empates.
Problemas similares
Problemas que usan las mismas ideas. Resolver dos o tres es lo que fija un patrón.
Python
def topKFrequent(nums, k):
# Escribe el código aquíCaso 1
Caso 2
Caso 3
Entrada
nums = [4, 1, 4, 2, 1, 4, 3, 1, 4] k = 2
Esperado
[4, 1]