Maximizar la mediana de una array

Dada una array de n elementos. La tarea es imprimir la array en una forma tal que la mediana de esa array sea máxima.

Ejemplos: 

Input: arr[] = {3, 1, 2, 3, 8}
Output: 3 1 8 2 3

Input: arr[] = {9, 8, 7, 6, 5, 4}
Output: 7 6 9 8 5 4

Enfoque: la mediana de cualquier secuencia es el elemento más central de la array dada. Por lo tanto, si la array tiene un número impar de elementos, el n/2 elemento es la mediana de la array y, en el caso, si la array tiene un número par de elementos, entonces n/2 y n/2 – 1 elemento son la mediana .
Para maximizar la mediana de cualquier array, en primer lugar, verifique si su tamaño es par o impar según el tamaño de la array, realice los siguientes pasos. 

  1. Si el tamaño es impar: encuentre el elemento máximo de la array e intercámbielo con el elemento n/2.
  2. Si el tamaño es par: busque los dos primeros elementos máximos e intercámbielos con n/2 y n/2-1 elementos.

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

C++

// C++ implementation of the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to print array with maximum median
void printMaxMedian(int arr[], int n)
{
    // case when size of array is odd
    if (n % 2) {
        int* maxElement = max_element(arr, arr + n);
        swap(*maxElement, arr[n / 2]);
    }
 
    // when the size of the array is even
    else {
        // find 1st maximum element
        int* maxElement1 = max_element(arr, arr + n);
 
        // find 2nd maximum element
        int* maxElement2 = max_element(arr, maxElement1);
        maxElement2 = max(maxElement2,
                          max_element(maxElement1 + 1, arr + n));
 
        // swap position for median
        swap(*maxElement1, arr[n / 2]);
        swap(*maxElement2, arr[n / 2 - 1]);
    }
 
    // print resultant array
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
}
 
// Driver code
int main()
{
    int arr[] = { 4, 8, 3, 1, 3, 7, 0, 4 };
    int n = sizeof(arr) / sizeof(arr[0]);
    printMaxMedian(arr, n);
 
    return 0;
}

Java

// Java implementation of the above approach
import java.util.*;
import java.lang.*;
import java.io.*;
 
class GFG{
 
public static int getIndexOfLargest(int[] array,
                                    int st,
                                    int n)
{
    if (array == null || array.length == 0)
     
        // null or empty
        return -1;
 
    int largest = st;
    for(int i = st + 1; i < n; i++)
    {
        if (array[i] > array[largest])
            largest = i;
    }
     
    // Position of the first largest
    // found
    return largest;
}
 
public static void swap(int a, int b, int[] arr)
{
    int temp = arr[a];
    arr[a] = arr[b];
    arr[b] = temp;
}
 
// Function to print array with maximum median
public static void printMaxMedian(int[] arr, int n)
{
     
    // Case when size of array is odd
    if (n % 2 != 0)
    {
        int maxElement = getIndexOfLargest(
            arr, 0, arr.length);
             
        swap(maxElement, n / 2, arr);
    }
 
    // When the size of the array is even
    else
    {
         
        // Find 1st maximum element
        int maxElement1 = getIndexOfLargest(
            arr, 0, arr.length);
 
        // Find 2nd maximum element
        int maxElement2 = getIndexOfLargest(
            arr, 0, maxElement1);
             
        maxElement2 = Math.max(
            arr[maxElement2],
            getIndexOfLargest(arr, maxElement1 + 1,
                              arr.length));
 
        // Swap position for median
        swap(maxElement1, n / 2, arr);
        swap(maxElement2, n / 2 - 1, arr);
    }
 
    // Print resultant array
    for(int i = 0; i < n; i++)
        System.out.print(arr[i] + " ");
}
 
// Driver Code
public static void main(String[] args)
    throws java.lang.Exception
{
    int arr[] = { 4, 8, 3, 1, 3, 7, 0, 4 };
 
    printMaxMedian(arr, arr.length);
}
}
 
// This code is contributed by grand_master

Python3

# Python3 implementation of the above approach
 
# Function to print the array with
# maximum median
def printMaxMedian(arr, n):
 
    # case when size of the array is odd
    if n % 2 != 0:
        maxElement = arr.index(max(arr))
        (arr[maxElement],
         arr[n // 2]) = (arr[n // 2],
                         arr[maxElement])
 
    # when size of array is even
    else:
         
        # find 1st maximum element
        maxElement1 = arr.index(max(arr))
 
        # find 2nd maximum element
        maxElement2 = arr.index(max(arr[0 : maxElement1]))
        maxElement2 = arr.index(max(arr[maxElement2],
                                max(arr[maxElement1 + 1:])))
 
        # swap position for median
        (arr[maxElement1],
         arr[n // 2]) = (arr[n // 2],
                         arr[maxElement1])
        (arr[maxElement2],
         arr[n // 2 - 1]) = (arr[n // 2 - 1],
                             arr[maxElement2])
 
    # print the resultant array
    for i in range(0, n):
        print(arr[i], end = " ")
 
# Driver code
if __name__ == "__main__":
 
    arr = [4, 8, 3, 1, 3, 7, 0, 4]
    n = len(arr)
    printMaxMedian(arr, n)
 
# This code is contributed by Rituraj Jain

C#

// C# implementation of the above approach
using System;
 
class GFG{
     
static int getIndexOfLargest(int[] array,
                             int st, int n)
{
    if (array == null || array.Length == 0)
     
        // Null or empty
        return -1;
  
    int largest = st;
    for(int i = st + 1; i < n; i++)
    {
        if (array[i] > array[largest])
            largest = i;
    }
      
    // Position of the first largest
    // found
    return largest;
}
  
static void swap(int a, int b, int[] arr)
{
    int temp = arr[a];
    arr[a] = arr[b];
    arr[b] = temp;
}
  
// Function to print array with maximum median
static void printMaxMedian(int[] arr, int n)
{
     
    // Case when size of array is odd
    if (n % 2 != 0)
    {
        int maxElement = getIndexOfLargest(
            arr, 0, arr.Length);
              
        swap(maxElement, n / 2, arr);
    }
  
    // When the size of the array is even
    else
    {
         
        // Find 1st maximum element
        int maxElement1 = getIndexOfLargest(
            arr, 0, arr.Length);
  
        // Find 2nd maximum element
        int maxElement2 = getIndexOfLargest(
            arr, 0, maxElement1);
              
        maxElement2 = Math.Max(
            arr[maxElement2],
            getIndexOfLargest(arr, maxElement1 + 1,
                              arr.Length));
  
        // Swap position for median
        swap(maxElement1, n / 2, arr);
        swap(maxElement2, n / 2 - 1, arr);
    }
  
    // Print resultant array
    for(int i = 0; i < n; i++)
        Console.Write(arr[i] + " ");
}
 
// Driver Code
static void Main()
{
    int[] arr = { 4, 8, 3, 1, 3, 7, 0, 4 };
     
    printMaxMedian(arr, arr.Length);
}
}
 
// This code is contributed by divyeshrabadiya07
Producción: 

4 3 3 7 8 1 0 4

 

Complejidad de tiempo: O(n), donde n es el tamaño de la array dada
Espacio auxiliar: O(1), ya que no se utiliza espacio adicional

Publicación traducida automáticamente

Artículo escrito por Shivam.Pradhan y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *