Programa C++ para reorganizar una array en forma mínima máxima: 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:

// C++ program to rearrange an array
// in minimum maximum form
#include <bits/stdc++.h>
using namespace std;
 
// Prints max at first position, min
// at second position second max at
// third position, second min at fourth
// position and so on.
void rearrange(int arr[], int n)
{
    // Initialize index of first minimum
    // and first maximum element
    int max_idx = n - 1, min_idx = 0;
 
    // Store maximum element of array
    int max_elem = arr[n - 1] + 1;
 
    // Traverse array elements
    for (int 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 (int i = 0; i < n; i++)
        arr[i] = arr[i] / max_elem;
}
 
// Driver code
int main()
{
    int arr[] = {1, 2, 3, 4,
                 5, 6, 7, 8, 9};
    int n = sizeof(arr) / sizeof(arr[0]);
 
    cout << "Original Array";
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
 
    rearrange(arr, n);
 
    cout <<
    "Modified Array";
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
    return 0;
}

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.

Gracias Saurabh Srivastava y Gaurav Ahirwar por sugerir este enfoque. 
Otro enfoque: un enfoque más simple será observar el posicionamiento de indexación de elementos máximos y elementos mínimos. El índice par almacena los elementos máximos y el índice impar almacena los elementos mínimos. Con cada índice creciente, el elemento máximo disminuye en uno y el elemento mínimo aumenta en uno. Se puede realizar un recorrido simple y arr[] se puede completar de nuevo.
Nota: Este enfoque solo es válido cuando los elementos de una array ordenada dada son consecutivos, es decir, varían en una unidad.
A continuación se muestra la implementación del enfoque anterior:

// C++ program to rearrange an array
// in minimum maximum form
#include <bits/stdc++.h>
using namespace std;
 
// Prints max at first position, min
// at second position second max at
// third position, second min at fourth
// position and so on.
void rearrange(int arr[], int n)
{
    // Initialize index of first minimum
    // and first maximum element
    int max_ele = arr[n - 1];
    int min_ele = arr[0];
     
    // Traverse array elements
    for (int i = 0; i < n; i++)
    {
        // At even index : we have to put
        // maximum element
        if (i % 2 == 0)
        {
            arr[i] = max_ele;
            max_ele -= 1;
        }
 
        // At odd index : we have to put
        // minimum element
        else
        {
            arr[i] = min_ele;
            min_ele += 1;
        }
    }
}
 
// Driver code
int main()
{
    int arr[] = {1, 2, 3, 4,
                 5, 6, 7, 8, 9};
    int n = sizeof(arr) / sizeof(arr[0]);
 
    cout <<
    "Original Array";
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
 
    rearrange(arr, n);
 
    cout <<
    "Modified Array";
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
    return 0;
}

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!