Reorganizar la array dada de modo que cada elemento no sea igual a la media de los elementos adyacentes

Dada una array arr que consta de N enteros únicos, la tarea es reorganizar la array de modo que el elemento en el índice i de la array no sea la media de los elementos adyacentes (es decir, del índice i-1 e i+1). Cualquier posible reordenamiento puede ser devuelto.

Ejemplo:

Entrada:  array = [5, 4, 3, 2, 1]
Salida:  [5, 3, 4, 2, 1]
Explicación: En la array de entrada:
Mean(5, 3) = (5 + 3)/2 = 4,
Media(4, 2) = (4+ 2 )/2 = 3,
Media(3, 1) = (3 + 1)/2 = 2.
Después de reorganizar la array como [5, 3, 4, 2, 1], ahora ningún elemento es la media de los elementos adyacentes: (5 + 4)/2 ≠ 3, (3 + 2)/2 ≠ 4, (4 + 1)/2 ≠ 2

Entrada: arr = [6, 9, 12, 25, 50 75]
Salida:  [6, 12, 9, 25, 50, 75]

Enfoque: La observación principal para resolver este problema es que para que 3 números a, b y c satisfagan la condición de que b no debe ser la media de a y c, [a, b, c] no debe ordenarse. Por lo tanto, este problema se puede resolver siguiendo los siguientes pasos:

• Iterar sobre la array de 1 a (N-1) 
• Comprobar si (arr[i – 1] + arr[i + 1]) / 2 == arr[i]) 
• Si se cumple la condición, intercambie los elementos arr[i] y arr[i+1]

A continuación se muestra la implementación del enfoque anterior:

// C++ code for above implementation
#include <bits/stdc++.h>
using namespace std;
 
// Function to rearrange the array
void Rearrange(int arr[], int N)
{
 
    // Iterating for array
    for (int i = 1; i < (N - 1); i++) {
 
        // Checking whether the element i
        // is mean of i-1 and i+1
        if ((arr[i - 1] + arr[i + 1]) / 2 == arr[i]) {
 
            // Rearrange by swapping arr[i] and arr[i+1]
            swap(arr[i], arr[i + 1]);
        }
    }
 
    // Printing the output array
    for (int i = 0; i < N; i++) {
        cout << arr[i] << " ";
    }
}
 
 
// Driver code
int main()
{
    int arr[] = { 6, 9, 12, 25, 50, 75 };
    int N = sizeof(arr) / sizeof(int);
 
    // calling the function
    Rearrange(arr, N);
    return 0;
}

// Java program for the above approach
 
import java.io.*;
 
class GFG {
  // Function to rearrange the array
   
static void Rearrange(int arr[], int N)
{
   
    // Iterating for array
    for (int i = 1; i < (N - 1); i++) {
   
        // Checking whether the element i
        // is mean of i-1 and i+1
        if ((arr[i - 1] + arr[i + 1]) / 2 == arr[i]) {
   
            // Rearrange by swapping arr[i] and arr[i+1]
            
          int temp = arr[i];
        arr[i] = arr[i + 1];
        arr[i + 1] = temp;
        }
    }
   
    // Printing the output array
    for (int i = 0; i < N; i++) {
         System.out.print(arr[i] +" ");
    }
}
   
// Driver code
    public static void main (String[] args) {
      int arr[] = { 6, 9, 12, 25, 50, 75 };
    int N = arr.length;
   
    // calling the function
    Rearrange(arr, N);
    }
}
// This code is contributed by Potta Lokesh

// C# program for the above approachusing System;class GFG {// Function to rearrange the arraystatic void Rearrange(int []arr, int N){// Iterating for arrayfor (int i = 1; i < (N – 1); i++) {// Checking whether the element i// is mean of i-1 and i+1if ((arr[i – 1] + arr[i + 1]) / 2 == arr[i]) {// Rearrange by swapping arr[i] and arr[i+1]int temp = arr[i];arr[i] = arr[i + 1];arr[i + 1] = temp;}}// Printing the output arrayfor (int i = 0; i < N; i++) {Console.Write(arr[i] +" ");}}// Driver codepublic static void Main (String[] args){int []arr = { 6, 9, 12, 25, 50, 75 };int N = arr.Length;// calling the functionRearrange(arr, N);}}// This code is contributed by shivanisinghss2110

# Python3 program for the above approach
 
# Function to rearrange the array
def Rearrange(arr, N) :
 
    # Iterating for array
    for i in range(1, N - 1) :
 
        # Checking whether the element i
        # is mean of i-1 and i+1
        if ((arr[i - 1] + arr[i + 1]) // 2 == arr[i]) :
 
            # Rearrange by swapping arr[i] and arr[i+1]
            arr[i], arr[i + 1] = arr[i + 1], arr[i];
 
    # Printing the output array
    for i in range(N) :
        print(arr[i],end= " " )
   
 
 
# Driver code
if __name__ == "__main__" :
 
    arr = [ 6, 9, 12, 25, 50, 75 ];
    N = len(arr);
 
    # calling the function
    Rearrange(arr, N);
     
    # This code is contributed by AnkThon

<script>
// JavaScript program for the above approach
// Function to rearrange the array
 
function Rearrange(arr, N)
{
 
    // Iterating for array
    for (var i = 1; i < (N - 1); i++) {
 
        // Checking whether the element i
        // is mean of i-1 and i+1
        if ((arr[i - 1] + arr[i + 1]) / 2 == arr[i]) {
 
            // Rearrange by swapping arr[i] and arr[i+1]
             
        var temp = arr[i];
        arr[i] = arr[i + 1];
        arr[i + 1] = temp;
        }
    }
 
    // Printing the output array
    for (var i = 0; i < N; i++) {
        document.write(arr[i] +" ");
    }
}
 
// Driver code
var arr = [ 6, 9, 12, 25, 50, 75 ];
var N = arr.length;
 
// calling the function
Rearrange(arr, N);
     
// This code is contributed by shivanisinghss2110
 
</script>

6 12 9 25 75 50 

Complejidad temporal: O(N)
Espacio auxiliar: O(1)