Encuentre la mediana para cada elemento de la array excluyendo el índice en el que se calcula la mediana

Dada una array A[] de N enteros donde N es par, . la tarea es generar una array de medianas donde la mediana de la array se calcula tomando la mediana de la array A[] excluyendo el elemento A[i]-ésimo .

Ejemplos:

Entrada N = 4, A = [2, 4, 4, 3]
Salida: [4, 3, 3, 4]
Explicación: mediana después de eliminar A[0]: la nueva array ordenada será [3, 4, 4]. Mediana = 4. 
Mediana después de eliminar A[1]: la nueva array ordenada será [2, 3, 4]. Mediana = 3. 
Mediana después de eliminar A[0]: la nueva array ordenada será [2, 3, 4]. Mediana = 3. 
Mediana después de eliminar A[0]: la nueva array ordenada será [2, 4, 4]. Mediana = 4.

Entrada: N = 6, A = [5, 5, 4, 4, 3, 3]
Salida: [4, 4, 4, 4, 4, 4]

Enfoque ingenuo: para cada i en el rango [0, N), elimine el elemento actual y ordene la array restante y luego calcule la mediana de la nueva array.
Complejidad de tiempo: O(N*N*log(N))
Espacio auxiliar: O(N)

Enfoque eficiente: como N es par, hay dos elementos centrales en la array actual que pueden ser la mediana de la array actual. Al eliminar cualquiera de los elementos, habrá un número impar de elementos y uno de los elementos centrales siempre será la respuesta. Denotemos los dos valores centrales como L y R . Hay 2 casos posibles: cuando la A[i] actual <=L , entonces R será la mediana final de la array. De lo contrario, cuando la corriente A[i] >= R entonces L será la mediana final de la array. Siga los pasos a continuación para resolver el problema:

• Inicialice una array B[] para almacenar las posiciones originales de los elementos en la array.
• Iterar sobre el rango [0, N) usando la variable i y realizar los siguientes pasos:
  • Almacene A[i] en la nueva array B[i].
• Ordene la array A[] para encontrar los elementos centrales.
• Iterar sobre el rango [0, N) usando la variable i y realizar los siguientes pasos:
  • Si B[i] es menor que L, entonces R será la mediana de la array excluyendo A[i].
  • De lo contrario, L será la mediana requerida.

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

// C++ Program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to return Median array after
// excluding each individual element
int findMedianExcludedArray(int A[], int N)
{
 
    // Store the original array in another
    // array to store the sorted version
    // and the original position of the array
    // element is also important
    int B[N];
    for (int i = 0; i < N; i++) {
        B[i] = A[i];
    }
 
    // Sort the original array
    sort(A, A + N);
 
    // Stores the left median
    int L = A[N / 2 - 1];
 
    // Stores the right median
    int R = A[N / 2];
 
    // Iterate over the range
    for (int i = 0; i < N; i++) {
 
        // If A[i] is less than equal to L,
        // then after removing it, R will become
        // the central element, otherwise L
        if (B[i] <= L) {
            cout << R;
        }
        else {
            cout << L;
        }
        if (i != N - 1) {
            cout << ", ";
        }
    }
 
    return 0;
}
 
// Driver Code
int main()
{
    int N = 4;
    int A[] = { 2, 4, 4, 3 };
    findMedianExcludedArray(A, N);
}

// Java code for above approach
import java.util.*;
 
class GFG{
 
// Function to return Median array after
// excluding each individual element
static int findMedianExcludedArray(int[] A, int N)
{
 
    // Store the original array in another
    // array to store the sorted version
    // and the original position of the array
    // element is also important
    int[] B = new int[N];
    for (int i = 0; i < N; i++) {
        B[i] = A[i];
    }
 
    // Sort the original array
    Arrays.sort(A);
 
    // Stores the left median
    int L = A[N / 2 - 1];
 
    // Stores the right median
    int R = A[N / 2];
 
    // Iterate over the range
    for (int i = 0; i < N; i++) {
 
        // If A[i] is less than equal to L,
        // then after removing it, R will become
        // the central element, otherwise L
        if (B[i] <= L) {
             System.out.print(R);
        }
        else {
             System.out.print(L);
        }
        if (i != N - 1) {
             System.out.print(", ");
        }
    }
 
    return 0;
}
 
// Driver Code
public static void main(String[] args)
{
    int N = 4;
    int[] A = { 2, 4, 4, 3 };
    findMedianExcludedArray(A, N);
}
}
 
// This code is contributed by target_2.

# Function to return Median array after
# excluding each individual element
def findMedianExcludedArray(A, N):
   
    # Store the original array in another
    # array to store the sorted version
    # and the original position of the array
    # element is also important
    B = []
    for i in range(N):
        B.append(A[i])
         
        # sort the original array
    A.sort()
     
    # Stores the left median
    L = A[N//2 - 1]
     
    # Stores the right median
    R = A[N//2]
     
     # Iterate over the range
    for i in range(N):
       
         # If A[i] is less than equal to L,
        # then after removing it, R will become
        # the central element, otherwise L
        if B[i] <= L:
            print(R, end="")
        else:
            print(L, end="")
        if i != N-1:
            print(", ", end="")
 
# Driver code
N = 4
A = [2, 4, 4, 3]
findMedianExcludedArray(A, N)
 
# This code is contributed by Parth Manchanda

// C# program for above approach
using System;
 
class GFG{
 
// Function to return Median array after
// excluding each individual element
static int findMedianExcludedArray(int[] A, int N)
{
 
    // Store the original array in another
    // array to store the sorted version
    // and the original position of the array
    // element is also important
    int[] B = new int[N];
    for (int i = 0; i < N; i++) {
        B[i] = A[i];
    }
 
    // Sort the original array
    Array.Sort(A);
 
    // Stores the left median
    int L = A[N / 2 - 1];
 
    // Stores the right median
    int R = A[N / 2];
 
    // Iterate over the range
    for (int i = 0; i < N; i++) {
 
        // If A[i] is less than equal to L,
        // then after removing it, R will become
        // the central element, otherwise L
        if (B[i] <= L) {
             Console.Write(R);
        }
        else {
             Console.Write(L);
        }
        if (i != N - 1) {
             Console.Write(", ");
        }
    }
 
    return 0;
}
 
// Driver Code
static void Main()
{
    int N = 4;
    int[] A = { 2, 4, 4, 3 };
    findMedianExcludedArray(A, N);
}
}
 
// This code is contributed by sanjoy_62.

<script>
 
// JavaScript program for the above approach
 
// Function to return Median array after
// excluding each individual element
function findMedianExcludedArray(A, N)
{
 
    // Store the original array in another
    // array to store the sorted version
    // and the original position of the array
    // element is also important
    let B = new Array(N);
    for (let i = 0; i < N; i++) {
        B[i] = A[i];
    }
 
    // Sort the original array
    A.sort();
 
    // Stores the left median
    let L = A[N / 2 - 1];
 
    // Stores the right median
    let R = A[N / 2];
 
    // Iterate over the range
    for (let i = 0; i < N; i++) {
 
        // If A[i] is less than equal to L,
        // then after removing it, R will become
        // the central element, otherwise L
        if (B[i] <= L) {
             document.write(R);
        }
        else {
             document.write(L);
        }
        if (i != N - 1) {
             document.write(", ");
        }
    }
 
    return 0;
}
 
// Driver Code
 
    let N = 4;
    let A = [ 2, 4, 4, 3 ];
    findMedianExcludedArray(A, N);
 
// This code is contributed by splevel62.
</script>

4, 3, 3, 4

Complejidad de tiempo: O(N*log(N))
Espacio auxiliar: O(N)