Kth Largest Element in an Array
Recibes un arreglo de números enteros nums y un número entero k. Devuelve el valor más grande número k de nums: el valor en la posición k, contando desde 1, una vez que el arreglo esté ordenado de mayor a menor.
Los valores iguales cuentan por separado. En [5, 5, 1], el valor más grande es 5 y el segundo más grande también es 5.
Función
- numsinteger-array
- los valores que se deben clasificar
- kinteger
- qué valor máximo devolver, 1 para el mayor
- Devuelveinteger
- el valor k-ésimo más grande, contando los duplicados
Restricciones
1 ≤ k ≤ nums.length ≤ 104-104 ≤ nums[i] ≤ 104- Los valores iguales cuentan como valores separados.
Ejemplos
- Entrada
- nums = [7, 2, 9, 4, 9, 1]k = 2
- Salida
- 9
- Explicación
- De mayor a menor, los valores son
9, 9, 7, 4, 2, 1. Los dos 9 se cuentan por separado, así que el segundo valor más grande es9, no7.
- Entrada
- nums = [5, -3, 8, 0, 2]k = 4
- Salida
- 0
- Explicación
- De mayor a menor, los valores son
8, 5, 2, 0, -3, y el cuarto de ellos es0.
- Entrada
- nums = [6]k = 1
- Salida
- 6
- Explicación
- Con un valor y
k = 1, ese valor es el mayor.
+15 pruebas ocultas al enviar
Para ir más allá
Los valores llegan ahora de uno en uno. ¿Puedes informar de la mediana de todos los valores vistos hasta el momento después de cada llegada, en O(log n) de tiempo por valor?
Pistas
Ábrelas de una en una. Cada una revela un poco más.
Ordenada de mayor a menor, la respuesta está en una posición conocida. ¿Cuál? ¿Y necesitas todos los demás valores para saberlo?
El k-ésimo valor más grande es el menor de los
kvalores más grandes. Si conservas solo loskvalores más grandes vistos hasta ahora, ¿con cuál de ellos comparas un valor nuevo?Mantén un montículo mínimo de como máximo
kvalores. Un valor nuevo reemplaza al elemento superior cuando es mayor, y al final la respuesta es el elemento superior. Para un tiempo promedio deO(n), particiona alrededor de un pivote aleatorio como hace quicksort y conserva solo el lado que contiene el índicen-k.
Solución
Ordenar y leer una posición responde a la pregunta, y aquí es lo bastante rápido. Lo que un entrevistador quiere ver es cuánto puedes saltarte de ese ordenamiento, porque necesitas una posición, no todas las n. Un montículo mínimo de tamaño k conserva solo los valores que aún pueden ser la respuesta, y quickselect particiona como quicksort, pero solo sigue el lado que contiene la respuesta, lo que reduce el tiempo promedio a O(n).
Ordenar y leer una posición
Intuición
El k-ésimo valor más grande se define por el orden ordenado, así que produce ese orden. Ordenado de mayor a menor, [7, 2, 9, 4, 9, 1] se convierte en [9, 9, 7, 4, 2, 1], y el k-ésimo más grande se encuentra en el índice k-1. Para k = 2, ese es el índice 1, el segundo 9. Si tu ordenación pone primero el valor más pequeño, consulta en su lugar el índice n-k: el índice 4 de [1, 2, 4, 7, 9, 9] contiene el mismo 9.
Los duplicados no requieren un tratamiento especial: una ordenación conserva todas las copias, y cada copia ocupa su propia posición.
Con n = 10^4, una ordenación realiza unas n log n ≈ 1.3 × 10^5 comparaciones, lo que supera todas las pruebas. El inconveniente es que ordena los n valores cuando solo importa una posición. Los dos enfoques siguientes hacen menos trabajo de ese tipo.
Algoritmo
- Copia
numspara que el arreglo de quien llama se mantenga como estaba. - Ordena la copia. Usa una comparación numérica; algunos lenguajes comparan los números como texto de forma predeterminada.
- Devuelve el índice
k-1de un orden de mayor a menor, o el índicen-kde un orden de menor a mayor.
def findKthLargest(nums, k):
# Largest first: the k-th largest sits at index k-1.
ordered = sorted(nums, reverse=True)
return ordered[k - 1]Conserva los k elementos más grandes en un montículo mínimo
Intuición
El valor k-ésimo más grande es el menor de los k valores más grandes. Así que recorre nums una vez y conserva solo los k valores más grandes vistos hasta el momento en un montículo mínimo. La cima de un montículo mínimo es su valor más pequeño, que es exactamente la respuesta candidata.
Cuando llega un valor x y el montículo contiene menos de k valores, añádelo. De lo contrario, compara x con la cima. Si x no es mayor, al menos k de los valores que conservaste son tan grandes como x, así que x nunca puede ser la respuesta y lo omites. Si x es mayor, la cima deja de estar entre los k valores más grandes: reemplázala por x. En el ejemplo 2, con k = 4, los primeros cuatro valores llenan el montículo con 5, -3, 8, 0 y la cima es -3. Después, 2 supera a -3 y lo reemplaza; la cima pasa a ser 0, y 0 es la respuesta.
Cada valor requiere como máximo una operación del montículo de O(log k), así que el total es O(n log k) de tiempo y O(k) de memoria. Eso supera a ordenar cuando k es pequeño, y funciona con un flujo de datos: nunca necesitas todos los valores a la vez. Python tiene heapq, Java tiene PriorityQueue, C++ tiene priority_queue con greater, Go tiene container/heap, Rust tiene BinaryHeap con Reverse y PHP tiene SplMinHeap. El código para los demás lenguajes implementa el montículo en un arreglo, donde los hijos del índice i se encuentran en 2i+1 y 2i+2, o en 2i y 2i+1 en Lua y R, que cuentan desde 1.
Algoritmo
- Empieza con un montículo mínimo vacío.
- Para cada valor
x, añádelo mientras el montículo contenga menos dekvalores. - Una vez que contenga
k, reemplaza el elemento superior porxsolo cuandoxsea mayor que el elemento superior. - Después del último valor, devuelve el elemento superior del montículo.
import heapq
def findKthLargest(nums, k):
# A min-heap of the k largest values so far; its top is the smallest of them.
heap = []
for x in nums:
if len(heap) < k:
heapq.heappush(heap, x)
elif x > heap[0]:
heapq.heapreplace(heap, x) # drop the top, add x
return heap[0]Quickselect con una partición en tres vías
Intuición
Quicksort elige un pivote y particiona: los valores menores a su izquierda y los mayores a su derecha. Después de una partición, el pivote queda en su índice final ordenado, aunque ninguno de los dos lados esté ordenado todavía. Quickselect aprovecha ese hecho. En orden de menor a mayor, la respuesta está en el índice target = n-k. Después de una partición, target está a la izquierda del pivote, en el pivote o a su derecha, así que continúas por un lado y descartas el otro.
Para [7, 2, 9, 4, 9, 1] y k = 2, target es 6-2 = 4. Particiona alrededor de 4: 2 y 1 ocupan los índices 0 y 1, 4 ocupa el índice 2, y 7, 9, 9 ocupan los índices del 3 al 5. El índice 4 está a la derecha, así que conservas solo los índices del 3 al 5. Particiona esos valores alrededor de 9: 7 ocupa el índice 3 y ambos 9 ocupan los índices 4 y 5. El índice 4 contiene un 9, así que la respuesta es 9.
Usa una partición de tres vías: primero los valores menores que el pivote, después los valores iguales a él y, luego, los valores mayores que él, delimitados por lt y gt. El bloque de iguales [lt, gt] ya está en su posición ordenada, así que, si target cae dentro de él, ya terminaste. Con una partición simple de dos vías, un arreglo con 10^4 copias de 7 se reduce en un valor por ronda, unas 5 × 10^7 operaciones; la versión de tres vías lo resuelve en una pasada.
Elige el pivote al azar. La mitad de las veces queda en la mitad central del rango, lo que reduce el rango a como máximo tres cuartos, así que el trabajo esperado es de unas pocas pasadas sobre n valores: O(n). El peor caso sigue siendo O(n²) si cada pivote es un valor extremo, y una elección fija, como el primer elemento, produce ese caso con una entrada ordenada. El código trabaja sobre una copia, lo que cuesta O(n) de memoria; particionar nums directamente reduce ese coste a O(1) si puedes modificar la entrada.
Algoritmo
- Copia
numsena, establecetarget = n-k,lo = 0yhi = n-1. - Elige un pivote aleatorio de
a[lo..hi]. - Particiona
a[lo..hi]en valores menores que, iguales a y mayores que el pivote, dejando los valores iguales ena[lt..gt]. - Si
target < lt, establecehi = lt-1; sitarget > gt, establecelo = gt+1; de lo contrario, devuelve el pivote. - Repite desde el paso 2.
import random
def findKthLargest(nums, k):
a = list(nums)
target = len(a) - k # the answer's index once a is sorted smallest first
lo, hi = 0, len(a) - 1
while True:
pivot = a[random.randint(lo, hi)]
# Three-way partition of a[lo..hi]: < pivot, then == pivot, then > pivot.
lt, i, gt = lo, lo, hi
while i <= gt:
if a[i] < pivot:
a[lt], a[i] = a[i], a[lt]
lt += 1
i += 1
elif a[i] > pivot:
a[i], a[gt] = a[gt], a[i]
gt -= 1
else:
i += 1
# Now a[lt..gt] all equal pivot, and they are in their sorted places.
if target < lt:
hi = lt - 1
elif target > gt:
lo = gt + 1
else:
return pivot
Errores comunes y casos límite
La mayoría de las respuestas incorrectas se deben a los duplicados y a confundir las dos formas de contar las posiciones.
- Eliminar primero los duplicados. El problema cuenta cada copia: en
[7, 2, 9, 4, 9, 1]conk = 2, la respuesta es9, pero después de convertir el arreglo en un conjunto, pasa a ser7. - Leer el índice equivocado.
kcuenta desde 1, así que la respuesta está en el índicek-1si el orden es de mayor a menor y en el índicen-ksi es de menor a mayor, no enn-k-1. - Ordenar los números como texto. En JavaScript y TypeScript,
[10, 9, 2].sort()da como resultado[10, 2, 9]. Pasa(a, b) => a - b. - Usar un montículo máximo de tamaño
k. Eliminar el valor más grande mantiene loskvalores más pequeños y devuelve el k-ésimo más pequeño. - Usar Quickselect con una partición de dos vías o un pivote fijo. Muchos valores iguales o un arreglo ordenado hacen que cueste
O(n²), algo que incluyen las pruebas grandes.
Preguntas frecuentes4
¿Cuál es la complejidad temporal de Kth Largest Element in an Array?
La ordenación tarda O(n log n). Un montículo mínimo de tamaño k tarda O(n log k) y requiere O(k) de memoria. Quickselect con un pivote aleatorio tarda O(n) en promedio y O(n²) en el peor caso, algo que un pivote aleatorio hace muy improbable.
¿Por qué usar un montículo mínimo, y no un montículo máximo, para encontrar el k-ésimo elemento más grande?
El montículo almacena los k valores más grandes vistos hasta ahora, y el valor con el que debes comparar y que debes expulsar es el más pequeño de ellos. Un montículo mínimo mantiene ese valor en la cima. Un montículo máximo solo funciona si introduces en él los n valores y extraes elementos k-1 veces, lo que requiere O(n) memoria.
¿Debería usar un montículo o quickselect para encontrar el k-ésimo elemento más grande?
Quickselect es más rápido en promedio, O(n), pero necesita todos los valores en memoria y los reordena. El heap es O(n log k) y no tiene un peor caso desfavorable, y funciona cuando los valores llegan de uno en uno y no puedes almacenarlos todos. En una entrevista, explica ambos y programa el que te pidan en la pregunta de seguimiento.
¿Se puede encontrar el k-ésimo elemento más grande en tiempo lineal en el peor de los casos?
Sí. La regla de mediana de medianas elige un pivote que garantiza descartar una proporción fija de los valores, lo que hace que la selección sea O(n) en el peor de los casos, aunque en la práctica es más lenta que un pivote aleatorio. Como los valores están limitados de -10^4 a 10^4, también puedes contar cuántas veces aparece cada valor y recorrerlos desde 10^4 hacia abajo hasta haber pasado k valores, en O(n + 2 × 10^4) de tiempo.
Problemas similares
Problemas que usan las mismas ideas. Resolver dos o tres es lo que fija un patrón.
Python
def findKthLargest(nums, k):
# Escribe el código aquíCaso 1
Caso 2
Caso 3
Entrada
nums = [7, 2, 9, 4, 9, 1] k = 2
Esperado
9