Second Largest Number

+10

Recibes una lista de enteros nums. Devuelve su segundo valor distinto más grande: el valor más grande que sea estrictamente menor que el máximo. Los valores pueden repetirse, así que para [5, 5, 3] la respuesta es 3, no 5. La lista siempre contiene al menos dos valores diferentes.

Función

secondLargest(nums: integer-array) → integer

numsinteger-array: la lista de números enteros, con al menos dos valores distintos
Devuelveinteger: el valor más grande que es menor que el máximo

Restricciones

2 ≤ nums.length ≤ 5000
-10⁹ ≤ nums[i] ≤ 10⁹
nums contiene al menos dos valores distintos.

Ejemplos

Entrada: nums = [4, 9, 2, 7, 9]
Salida: 7
Explicación: El máximo es 9. Aparece dos veces, pero una segunda copia del máximo no cuenta, así que la respuesta es el siguiente valor más bajo, 7.

Entrada: nums = [-5, -1, -8]
Salida: -5
Explicación: De mayor a menor, los valores son -1, -5, -8. El segundo mayor es -5, aunque sea negativo.

Entrada: nums = [6, 6, 6, 3]
Salida: 3
Explicación: Solo existen dos valores distintos, 6 y 3. Por muchas veces que se repita 6, el segundo más grande es 3.

Para ir más allá

¿Puedes devolver el tercer valor distinto más grande en una sola pasada, con tres variables y sin ordenar?

Pistas

Ábrelas de una en una. Cada una revela un poco más.

0 de 3 abiertas

Solución

Dos detalles hacen que esto sea más difícil que encontrar el máximo. El máximo puede repetirse, y una repetición no debe informarse como el segundo valor más grande. La respuesta puede ser negativa, así que una variable que comienza en 0 da una respuesta incorrecta en una lista con todos los valores negativos. Llevar un seguimiento de los dos valores distintos más grandes en una sola pasada, con comparaciones estrictas, resuelve ambos problemas.

Ordena y baja más allá del máximo

Intuición

Ordena una copia de menor a mayor. El máximo queda al final, posiblemente varias veces seguidas. Recorre hacia la izquierda desde el final, pasando por cada copia del máximo; el primer valor diferente es el segundo más grande. Para [6, 6, 6, 3], la copia ordenada es [3, 6, 6, 6]: te saltas tres 6 y llegas a 3.

Devolver el penúltimo elemento es el error clásico en este caso. Para [4, 9, 2, 7, 9], devuelve 9, el máximo otra vez. El recorrido no puede salirse por el principio, porque la lista contiene al menos dos valores distintos.

La respuesta es correcta, pero ordenar organiza todos los valores cuando solo te interesan los dos mayores. Cuesta O(n log n) de tiempo y la copia ocupa O(n) de memoria.

Algoritmo

Copia nums y ordena la copia de menor a mayor.
Empieza con el índice i en la última posición.
Mientras el valor en i sea igual al máximo, mueve i un paso a la izquierda.
Devuelve el valor en i.

def secondLargest(nums):
    ordered = sorted(nums)
    i = len(ordered) - 1
    # Step left past every copy of the maximum.
    while ordered[i] == ordered[-1]:
        i -= 1
    return ordered[i]

Dos pasadas

Intuición

Divide el trabajo en dos partes. La primera pasada encuentra el máximo, como en Buscar el número más grande. La segunda pasada busca el valor más grande que sea estrictamente menor que ese máximo. Para [4, 9, 2, 7, 9], la primera pasada encuentra 9 y la segunda omite ambos 9 y conserva el mayor de 4, 2 y 7, que es 7.

Inicia second por debajo de cualquier valor que pueda contener la lista, como el entero más pequeño que tenga tu lenguaje. La lista tiene al menos dos valores distintos, así que algún valor es menor que el máximo y siempre reemplaza ese valor inicial.

Cada pasada calcula un máximo acumulado, por lo que el total es O(n) de tiempo y O(1) de espacio. El costo es leer la lista dos veces, lo cual es imposible cuando los valores llegan de uno en uno y desaparecen después de leerlos.

Algoritmo

Recorre nums una vez y guarda el máximo en largest.
Establece second por debajo de todos los valores permitidos.
Vuelve a recorrer. Para cada x que cumpla x < largest y x > second, establece second en x.
Devuelve second.

def secondLargest(nums):
    largest = nums[0]
    for x in nums:
        if x > largest:
            largest = x
    second = float("-inf")  # below every allowed value
    for x in nums:
        if x < largest and x > second:
            second = x
    return second

Un recorrido para llevar el seguimiento de los dos valores más altos

Intuición

Mantén dos variables, largest y second, para los dos valores distintos más altos vistos hasta ahora. Cada nuevo valor x corresponde a uno de tres casos. Si x es mayor que largest, el antiguo largest pasa al segundo puesto y x ocupa el primero. Si x está estrictamente entre second y largest, se convierte en el nuevo second. En cualquier otro caso, nada cambia.

Las comparaciones estrictas son las que permiten manejar los duplicados. Para [4, 9, 2, 7, 9]: largest pasa a ser 4, después 9, con second = 4. 2 no cambia nada, 7 está entre 4 y 9, así que second = 7, y el último 9 es igual a largest, así que se omite. La respuesta es 7.

Inicializa ambas variables con un valor menor que cualquier valor posible. Inicializarlas con 0 devuelve 0 para [-5, -1, -8], porque ningún valor supera jamás a 0. Como la lista contiene dos valores distintos, second siempre termina siendo un valor real de la lista.

Algoritmo

Establece largest y second por debajo de todos los valores permitidos.
Recorre todos los valores x de nums.
Si x > largest, mueve largest a second y establece largest en x.
En caso contrario, si x < largest y x > second, establece second en x.
Después del bucle, devuelve second.

def secondLargest(nums):
    # Both start below every allowed value.
    largest = second = float("-inf")
    for x in nums:
        if x > largest:
            second = largest  # the old maximum drops to second place
            largest = x
        elif largest > x > second:
            second = x
    return second

Errores comunes y casos límite

La mayoría de las respuestas incorrectas se deben a duplicados del valor máximo o a valores negativos.

Devolver el penúltimo elemento de la lista ordenada. Si el máximo está repetido, como en [4, 9, 2, 7, 9], ese elemento vuelve a ser el máximo.
Iniciar las variables en 0. En [-5, -1, -8], ningún valor supera 0, y devuelves 0, un número que no está en la lista.
Escribir x >= largest en el primer caso. Un segundo 9 hace que el primer 9 pase a second, y devuelves 9.
Actualizar second solo cuando aparece un nuevo máximo. En [10, 20, 15], el 15 nunca llega a second, y devuelves 10.
Eliminar los duplicados con un conjunto y luego ordenar. Funciona, pero consume O(n) de memoria y O(n log n) de tiempo para una tarea que se resuelve con una sola pasada.

Preguntas frecuentes3

¿Cómo encuentras el segundo número más grande de un array en una sola pasada?

Mantén los valores distintos más grandes y los segundos más grandes vistos hasta el momento. Cuando un valor supera al más grande, el antiguo más grande pasa al segundo lugar. Cuando un valor queda estrictamente entre los dos, reemplaza al segundo. Después de una pasada, la segunda variable contiene la respuesta.

¿Cuál es la complejidad temporal de encontrar el segundo elemento más grande?

Los métodos de una pasada y de dos pasadas requieren ambos un tiempo de O(n) y un espacio extra de O(1). Ordenar primero requiere un tiempo de O(n log n). No puedes superar O(n), porque hay que leer cada valor al menos una vez.

¿Cómo afectan los duplicados al segundo elemento más grande?

Este problema pide el segundo valor distinto más grande, así que se omiten las copias del máximo. Para [9, 9, 7], la respuesta es 7. Algunas versiones de la pregunta cuentan las posiciones y responderían 9, así que comprueba cuál de las dos interpretaciones se pretende antes de programar.

def secondLargest(nums):
    # Escribe el código aquí

Prueba #1

Prueba #2

Prueba #3

Argumento

nums = [4, 9, 2, 7, 9]

Salida Esperada

Second Largest Number

Función

Restricciones

Ejemplos

Pistas

Solución

Ordena y baja más allá del máximo

Dos pasadas

Un recorrido para llevar el seguimiento de los dos valores más altos

Errores comunes y casos límite

Preguntas frecuentes3

Problemas similares