¿Escribir un programa para obtener el segundo número más alto en una array usando PHP?

Dada una array de enteros, la tarea es escribir un programa que encuentre de manera eficiente el segundo elemento más grande presente en la array.  

Ejemplo:

Input: arr[] = {13, 14, 15, 16, 17, 18}
Output: The second largest element is 17.
Explanation: The largest element of the array
is 35 and the second largest element is 17

Input: arr[] = {10, 5, 10}
Output: The second largest element is 5.
Explanation: The largest element of the array
is 10 and the second largest element is 5

Input: arr[] = {10, 10, 10}
Output: The second largest does not exist.
Explanation: Largest element of the array  
is 10 there is no second largest element

Solución simple:

Enfoque: la idea es ordenar la array en orden descendente y luego devolver el segundo elemento que no es igual al elemento más grande de la array ordenada.

<?php
function bubbleSort(&$arr) {
    $n = sizeof($arr);
  
    // Traverse through all array elements
    for($i = 0; $i < $n; $i++) {
        $swapped = False;
  
        // Last i elements are already
        // in place
        for ($j = 0; $j < $n - $i - 1; $j++) {
              
            // traverse the array from 0 to
            // n-i-1. Swap if the element
            // found is greater than the
            // next element
            if ($arr[$j] <$arr[$j+1]) {
                $t = $arr[$j];
                $arr[$j] = $arr[$j+1];
                $arr[$j+1] = $t;
                $swapped = True;
            }
        }
  
        // IF no two elements were swapped
        // by inner loop, then break
        if ($swapped == False)
            break;
    }
}
          
// Driver code to test above
$arr = array(64, 34, 25, 12, 22, 11, 90);
$len = sizeof($arr);
bubbleSort($arr);
  
if($arr[0] == $arr[1]) {
  echo "No element";
}
else {
  echo "Second Largest element is ".$arr[1];
}
      
?>

Second Largest element is 64

Análisis de Complejidad:

Complejidad de tiempo de peor caso y promedio: O(n*n). El peor de los casos ocurre cuando la array se ordena de forma inversa.
Complejidad temporal del mejor caso: O(n). El mejor de los casos ocurre cuando la array ya está ordenada.
Espacio Auxiliar: O(1)

Casos límite: la ordenación de burbujas toma un tiempo mínimo (Orden de n) cuando los elementos ya están ordenados.
Clasificación en el lugar: Sí
Estable : Sí

Otro enfoque: encuentre el segundo elemento más grande en un solo recorrido.  

A continuación se muestra el algoritmo completo para hacer esto:  

1) Initialize the first as 0 (i.e, index of arr[0] element)
2) Start traversing the array from array[1],
  a) If the current element in array say arr[i] is greater
     than first. Then update first and second as,
     second = first
     first = arr[i]
  b) If the current element is in between first and second,
     then update second to store the value of current variable as
     second = arr[i]
3) Return the value stored in second.

<?php
    
// PHP program to find second largest
// element in an array
  
// Function to print the
// second largest elements
function print2largest($arr, $arr_size) {
  
    // There should be atleast
    // two elements
    if ($arr_size < 2) {
        echo(" Invalid Input ");
        return;
    }
  
    $first = $second = PHP_INT_MIN;
    
    for ($i = 0; $i < $arr_size ; $i++) {
          
        // If current element is
        // smaller than first
        // then update both
        // first and second
        if ($arr[$i] > $first) {
            $second = $first;
            $first = $arr[$i];
        }
  
        // If arr[i] is in
        // between first and
        // second then update
        // second
        else if ($arr[$i] > $second &&
                $arr[$i] != $first)
            $second = $arr[$i];
    }
    if ($second == PHP_INT_MIN)
        echo("There is no second largest element\n");
    else
        echo("The second largest element is "
                 . $second . "\n");
}
  
// Driver Code
$arr = array(12, 35, 1, 10, 34, 1);
$n = sizeof($arr);
print2largest($arr, $n);
  
?>

The second largest element is 34