Programa C++ 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.
      

// C++ program to find third Largest
// element in an array of distinct elements
#include <bits/stdc++.h>
  
void thirdLargest(int arr[], int arr_size)
{
    /* There should be atleast three elements */
    if (arr_size < 3)
    {
        printf(" Invalid Input ");
        return;
    }
  
    // Find first largest element
    int first = arr[0];
    for (int i = 1; i < arr_size ; i++)
        if (arr[i] > first)
            first = arr[i];
  
    // Find second largest element
    int second = INT_MIN;
    for (int i = 0; i < arr_size ; i++)
        if (arr[i] > second && arr[i] < first)
            second = arr[i];
  
    // Find third largest element
    int third = INT_MIN;
    for (int i = 0; i < arr_size ; i++)
        if (arr[i] > third && arr[i] < second)
            third = arr[i];
  
    printf("The third Largest element is %d
", third);
}
  
/* Driver program to test above function */
int main()
{
    int arr[] = {12, 13, 1, 10, 34, 16};
    int n = sizeof(arr)/sizeof(arr[0]);
    thirdLargest(arr, n);
    return 0;
}

• 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
      

// C++ program to find third 
// Largest element in an array
#include <bits/stdc++.h>
  
void thirdLargest(int arr[], int arr_size)
{
    /* There should be atleast three elements */
    if (arr_size < 3)
    {
        printf(" Invalid Input ");
        return;
    }
  
    // Initialize first, second and third Largest element
    int first = arr[0], second = INT_MIN, third = INT_MIN;
  
    // Traverse array elements to find the third Largest
    for (int i = 1; i < arr_size ; i ++)
    {
        /* 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 */
        else if (arr[i] > second)
        {
            third = second;
            second = arr[i];
        }
  
        /* If arr[i] is in between second and third */
        else if (arr[i] > third)
            third = arr[i];
    }
  
    printf("The third Largest element is %d
", third);
}
  
/* Driver program to test above function */
int main()
{
    int arr[] = {12, 13, 1, 10, 34, 16};
    int n = sizeof(arr)/sizeof(arr[0]);
    thirdLargest(arr, n);
    return 0;
}

• 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!