Find the Largest Number
Recibes una lista no vacía de números enteros nums. Devuelve el valor más grande de la lista. Los valores pueden ser negativos, así que la respuesta también puede ser negativa. Encuéntralo con tus propias comparaciones, sin usar una función de máximo integrada como max.
Función
- numsinteger-array
- la lista de enteros en la que buscar
- Devuelveinteger
- el valor más grande de nums
Restricciones
1 ≤ nums.length ≤ 5000-109 ≤ nums[i] ≤ 109
Ejemplos
- Entrada
- nums = [3, 17, 4, 12, 9]
- Salida
- 17
- Explicación
- Al leer de izquierda a derecha, el valor más grande hasta ahora es
3, después17. Ninguno de4,12o9supera a17, así que la respuesta es17.
- Entrada
- nums = [-8, -3, -11, -3]
- Salida
- -3
- Explicación
- Todos los valores son negativos, y
-3es el más cercano a cero, así que es el mayor. Aparece dos veces, pero devuelves el valor, no su posición.
- Entrada
- nums = [42]
- Salida
- 42
- Explicación
- Una lista con un valor tiene ese valor como el mayor.
+13 pruebas ocultas al enviar
Para ir más allá
¿Puedes devolver tanto el valor más grande como el más pequeño con aproximadamente 3n/2 comparaciones en lugar de 2n, comparando primero los valores por pares?
Pistas
Ábrelas de una en una. Cada una revela un poco más.
Lee los valores uno a la vez. ¿Qué es lo único que necesitas recordar sobre los valores que ya has visto?
Recuerda solo el valor más grande hasta el momento. Cada valor nuevo lo supera o no.
Inicializa el máximo actual con
nums[0], no con0, ya que todos los valores pueden ser negativos. Compáralo con cada valor y conserva el mayor.
Solución
Cualquier valor que omitas podría ser el más grande, así que toda solución lee cada elemento al menos una vez. La única decisión real es dónde comienza el máximo acumulado. Inicialízalo con el primer elemento, nunca con 0, porque todos los valores de la lista podrían ser negativos.
Ordena una copia y toma el último valor
Intuición
En una lista ordenada de menor a mayor, el valor más grande está al final. Copia nums para que la lista de quien llama se mantenga igual, ordena la copia y devuelve su último elemento. Para [3, 17, 4, 12, 9], la copia ordenada es [3, 4, 9, 12, 17], y el último elemento es 17.
La respuesta es correcta, pero ordenar hace mucho más de lo necesario. Coloca todos los valores en orden, lo que requiere alrededor de n log n comparaciones, aproximadamente 60,000 para n = 5000, cuando solo quieres el mayor. La copia también requiere O(n) de memoria.
En JavaScript y TypeScript, pasa un comparador a sort. Sin uno, compara los números como texto, lo que coloca 12 y 17 antes de 3.
Algoritmo
- Copia
nums. - Ordena la copia de menor a mayor, comparando los números como números.
- Devuelve el último elemento de la copia ordenada.
def findMax(nums):
ordered = sorted(nums) # a sorted copy, smallest first
return ordered[-1]Una pasada con un máximo acumulado
Intuición
Conserva una variable, largest, para el valor más grande encontrado hasta el momento. Asígnale inicialmente nums[0], compárala con cada valor y reemplázala cada vez que un valor sea mayor. Cuando termine el bucle, largest se habrá comparado con cada elemento, así que ningún valor de la lista lo supera.
Para [3, 17, 4, 12, 9], largest empieza en 3, pasa a ser 17 y se mantiene en 17 con 4, 12 y 9. Eso supone n-1 comparaciones útiles y una variable adicional.
Empezar en nums[0] es lo que permite que funcione con listas de números negativos. Si empiezas en 0, [-8, -3, -11, -3] nunca lo supera, así que devuelves 0, un valor que ni siquiera está en la lista.
Algoritmo
- Establece
largestennums[0]. - Recorre cada valor
xdenums. - Si
x > largest, establecelargestenx. - Después del bucle, devuelve
largest.
def findMax(nums):
largest = nums[0] # never 0: every value may be negative
for x in nums:
if x > largest:
largest = x
return largest
Errores comunes y casos límite
El bucle es corto, así que los errores están en dónde empieza y qué lee.
- Empezar
largesten0o-1. Cualquier lista cuyos valores estén todos por debajo de ese valor inicial devuelve un número que no está en la lista. - Empezar con un número pequeño inventado, como
-1000000. Los valores aquí bajan hasta-10^9, así que el valor inicial sigue siendo el mayor.nums[0]no requiere adivinar. - Leer
nums[0]en Lua o R, donde el primer elemento esnums[1]. Lua devuelvenily R devuelve un vector vacío. - Usar un bucle con
i ≤ nen un lenguaje con índices que empiezan en 0, lo que lee un elemento más allá del final. - Ordenar sin un comparador numérico en JavaScript o TypeScript. El orden textual de
[3, 17, 4, 12, 9]termina con9, así que devuelves9en lugar de17.
Preguntas frecuentes4
¿Cuál es la complejidad temporal de encontrar el máximo en un array?
Una pasada toma un tiempo de O(n) y un espacio extra de O(1). Ningún método aplicado a un arreglo sin ordenar puede hacerlo mejor, porque cualquier elemento que nunca leas podría ser el mayor. Ordenarlo primero cuesta O(n log n), lo cual es más lento y no aporta ninguna ventaja.
¿Cómo encuentras el número más grande de un arreglo sin usar max?
Guarda el primer elemento en una variable. Recorre el resto y, siempre que un elemento sea mayor que la variable, guarda ese elemento en su lugar. Cuando termine el bucle, la variable contendrá el valor más grande.
¿Por qué el máximo actual debería comenzar en el primer elemento y no en 0?
Si todos los valores son negativos, ninguno es mayor que 0, así que un máximo que empieza en 0 nunca cambia y la función devuelve 0. El primer elemento siempre es un candidato válido, así que empezar por ahí es correcto para cualquier lista. El entero más pequeño de tu lenguaje también sirve, siempre que la lista nunca esté vacía.
¿Cuándo es la ordenación una buena forma de encontrar el valor más grande?
Cuando necesitas más que el valor máximo, como los tres valores más grandes o la mediana, y vas a hacer muchas preguntas de este tipo sobre la misma lista. Para obtener un único máximo, una sola pasada es más rápida y deja la lista intacta.
Problemas similares
Problemas que usan las mismas ideas. Resolver dos o tres es lo que fija un patrón.
Python
def findMax(nums):
# Escribe el código aquíCaso 1
Caso 2
Caso 3
Entrada
nums = [3, 17, 4, 12, 9]
Esperado
17