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.
- Si el tamaño es impar: encuentre el elemento máximo de la array e intercámbielo con el elemento n/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