Programa Php para reorganizar una array en forma máxima mínima: conjunto 2 (O (1) espacio adicional)

Dada una array ordenada de enteros positivos, reorganice la array alternativamente, es decir, el primer elemento debe ser el valor máximo, el segundo valor mínimo, el tercer segundo máximo, el cuarto segundo mínimo y así sucesivamente. 
Ejemplos:
 

Entrada : arr[] = {1, 2, 3, 4, 5, 6, 7} 
Salida : arr[] = {7, 1, 6, 2, 5, 3, 4}
Entrada : arr[] = {1 , 2, 3, 4, 5, 6} 
Salida : arr[] = {6, 1, 5, 2, 4, 3} 

Hemos discutido una solución en la publicación a continuación: 
Reorganizar una array en forma mínima máxima | Conjunto 1 : la solución discutida aquí requiere espacio adicional, cómo resolver este problema con O (1) espacio adicional.

En esta publicación se analiza una solución que requiere O(n) tiempo y O(1) espacio adicional. La idea es usar la multiplicación y el truco modular para almacenar dos elementos en un índice. 

even index : remaining maximum element.
odd index  : remaining minimum element.
 
max_index : Index of remaining maximum element
            (Moves from right to left)
min_index : Index of remaining minimum element
            (Moves from left to right)

Initialize: max_index = 'n-1'
            min_index = 0  

            // Can be any element which is more than 
            // the maximum value in array
            max_element = arr[max_index] + 1 

For i = 0 to n-1            
    If 'i' is even
       arr[i] += (arr[max_index] % max_element * 
                  max_element) 
       max_index--     

    // if 'i' is odd
    ELSE 
       arr[i] +=  (arr[min_index] % max_element * 
                   max_element)
       min_index++

¿Cómo funciona la expresión “arr[i] += arr[max_index] % max_element * max_element” ? 
El propósito de esta expresión es almacenar dos elementos en el índice arr[i]. arr[max_index] se almacena como multiplicador y “arr[i]” se almacena como resto. Por ejemplo, en {1 2 3 4 5 6 7 8 9}, max_element es 10 y almacenamos 91 en el índice 0. Con 91, podemos obtener el elemento original como 91%10 y el elemento nuevo como 91/10.
Debajo de la implementación de la idea anterior:

<?php
// PHP program to rearrange an
// array in minimum-maximum form
 
// Prints max at first position, min
// at second position second max at
// third position, second min at fourth
// position and so on.
function rearrange(&$arr, $n)
{
    // Initialize index of first
    // minimum and first maximum element
    $max_idx = $n - 1; $min_idx = 0;
 
    // Store maximum element of array
    $max_elem = $arr[$n - 1] + 1;
 
    // Traverse array elements
    for ($i = 0; $i < $n; $i++)
    {
        // At even index : we have to
        // put maximum element
        if ($i % 2 == 0)
        {
            $arr[$i] += ($arr[$max_idx] %
                         $max_elem) * $max_elem;
            $max_idx--;
        }
 
        // At odd index : we have to
        // put minimum element
        else
        {
            $arr[$i] += ($arr[$min_idx] %
                         $max_elem) * $max_elem;
            $min_idx++;
        }
    }
 
    // Array elements back to
    // it's original form
    for ($i = 0; $i < $n; $i++)
        $arr[$i] = (int)($arr[$i] / $max_elem);
}
 
// Driver Code
$arr = array(1, 2, 3, 4, 5,
             6, 7, 8, 9);
$n = sizeof($arr);
 
echo "Original Array" . "";
for ($i = 0; $i < $n; $i++)
    echo $arr[$i] . " ";
 
rearrange($arr, $n);
 
echo "Modified Array";
for ($i = 0; $i < $n; $i++)
    echo $arr[$i] . " ";
// This code is contributed by Akanksha Rai(Abby_akku)

Producción : 

Original Array
1 2 3 4 5 6 7 8 9 
Modified Array
9 1 8 2 7 3 6 4 5 

Complejidad de tiempo: O (N), ya que estamos usando un bucle para atravesar N veces.

Espacio auxiliar: O(1), ya que no estamos utilizando ningún espacio adicional.

Consulte el artículo completo sobre Reorganizar una array en forma máxima mínima | ¡Establezca 2 (O (1) espacio adicional) para obtener más detalles!