Programa Python para el tercer elemento más grande en una array de elementos distintos

Dada una array de n enteros, encuentre el tercer elemento más grande. Todos los elementos de la array son enteros distintos. 
Ejemplo : 
 

Input: arr[] = {1, 14, 2, 16, 10, 20}
Output: The third Largest element is 14

Explanation: Largest element is 20, second largest element is 16 
and third largest element is 14

Input: arr[] = {19, -10, 20, 14, 2, 16, 10}
Output: The third Largest element is 16

Explanation: Largest element is 20, second largest element is 19 
and third largest element is 16

Enfoque ingenuo : la tarea es encontrar primero el elemento más grande, seguido del segundo elemento más grande y luego, excluyéndolos a ambos, encontrar el tercer elemento más grande. La idea básica es iterar la array dos veces y marcar el máximo y el segundo elemento máximo y luego, excluyéndolos a ambos, encontrar el tercer elemento máximo, es decir, el elemento máximo excluyendo el máximo y el segundo máximo.
 

• Algoritmo: 
  1. Primero, itere a través de la array y encuentre el máximo.
  2. Almacene esto como primer máximo junto con su índice.
  3. Ahora recorra toda la array encontrando el segundo máximo, excluyendo el elemento máximo.
  4. Finalmente, recorra la array por tercera vez y encuentre el tercer elemento más grande, es decir, excluyendo el máximo y el segundo máximo.
      

# Python 3 program to find 
# third Largest element in 
# an array of distinct elements
import sys
def thirdLargest(arr, arr_size):
  
    # There should be 
    # atleast three elements 
    if (arr_size < 3):
      
        print(" Invalid Input ")
        return
      
  
    # Find first 
    # largest element
    first = arr[0]
    for i in range(1, arr_size):
        if (arr[i] > first):
            first = arr[i]
  
    # Find second
    # largest element
    second = -sys.maxsize
    for i in range(0, arr_size):
        if (arr[i] > second and 
            arr[i] < first):
            second = arr[i]
  
    # Find third 
    # largest element
    third = -sys.maxsize
    for i in range(0, arr_size):
        if (arr[i] > third and
            arr[i] < second):
            third = arr[i]
  
    print("The Third Largest", 
          "element is", third)
  
# Driver Code
arr = [12, 13, 1, 
       10, 34, 16]
n = len(arr)
thirdLargest(arr, n)
  
# This code is contributed 
# by Smitha

• Producción: 
   

The third Largest element is 13

• Análisis de Complejidad: 
  • Complejidad temporal: O(n). 
    Como la array se itera tres veces y se realiza en un tiempo constante
  • Complejidad espacial: O(1). 
    No se necesita espacio adicional ya que los índices se pueden almacenar en un espacio constante.

Enfoque eficiente : el problema trata de encontrar el tercer elemento más grande en la array en un solo recorrido. El problema se puede resolver tomando la ayuda de un problema similar: encontrar el segundo elemento máximo . Entonces, la idea es recorrer la array de principio a fin y realizar un seguimiento de los tres elementos más grandes hasta ese índice (almacenados en variables) . Entonces, después de recorrer toda la array, las variables habrían almacenado los índices (o valores) de los tres elementos más grandes de la array.
 

• Algoritmo: 
  1. Cree tres variables, primero , segundo , tercero , para almacenar índices de los tres elementos más grandes de la array. (Inicialmente todos ellos se inicializan a un valor mínimo).
  2. Muévase a lo largo de la array de entrada desde el principio hasta el final.
  3. Para cada índice, compruebe si el elemento es más grande que el primero o no. Actualice el valor de first , si el elemento es más grande, y asigne el valor de first a second y second a third . Entonces, el elemento más grande se actualiza y los elementos previamente almacenados como más grandes se convierten en el segundo más grande, y el segundo elemento más grande se convierte en el tercero más grande.
  4. De lo contrario, si el elemento es más grande que el segundo , actualice el valor del segundo y el segundo elemento más grande se convierte en el tercero más grande.
  5. Si las dos condiciones anteriores fallan, pero el elemento es más grande que el tercero , actualice el tercero .
  6. Imprima el valor de tercero después de atravesar la array de principio a fin
      

# Python3 program to find 
# third Largest element in 
# an array
import sys
def thirdLargest(arr, arr_size):
  
    # There should be 
    # atleast three elements 
    if (arr_size < 3):
      
        print(" Invalid Input ")
        return
      
    # Initialize first, second
    # and third Largest element
    first = arr[0]
    second = -sys.maxsize
    third = -sys.maxsize
  
    # Traverse array elements
    # to find the third Largest
    for i in range(1, arr_size):
      
        # If current element is
        # greater than first,
        # then update first, 
        # second and third 
        if (arr[i] > first):
          
            third = second
            second = first
            first = arr[i]
          
  
        # If arr[i] is in between 
        # first and second 
        elif (arr[i] > second):
          
            third = second
            second = arr[i]
          
        # If arr[i] is in between
        # second and third 
        elif (arr[i] > third):
            third = arr[i]
      
    print("The third Largest" , 
                  "element is", third)
  
# Driver Code
arr = [12, 13, 1,
       10, 34, 16]
n = len(arr)
thirdLargest(arr, n)
  
# This code is contributed
# by Smitha

• Producción: 
   

The third Largest element is 13

• Análisis de Complejidad:
  • Complejidad temporal: O(n). 
    Como la array se itera una vez y se realiza en un tiempo constante
  • Complejidad espacial: O(1). 
    No se necesita espacio adicional ya que los índices se pueden almacenar en un espacio constante.

¡ Consulte el artículo completo sobre el tercer elemento más grande en una variedad de elementos distintos para obtener más detalles!