Maximice la mediana de la array dada después de agregar K elementos a la misma array

Dada una array arr[] de N elementos y un entero K donde K < N . La tarea es insertar K elementos enteros en la misma array de modo que se maximice la mediana de la array resultante. Imprime la mediana maximizada.
Ejemplos: 
 

Entrada: arr[] = {3, 2, 3, 4, 2}, k = 2 
Salida: 3 
{2, 2, 3, 3, 4, 5, 5} puede ser una vez una array resultante con 3 como mediana .
Entrada: arr[] = {3, 2, 3, 4, 2}, k = 3 
Salida: 3,5 
 

Enfoque: para maximizar la mediana de la array resultante, todos los elementos que deben insertarse deben ser mayores que el elemento máximo de la array. Después de insertar estos elementos, el nuevo tamaño de la array será size = N + K . Ordene la array y la mediana de la array será arr[tamaño/2] si el tamaño es impar de lo contrario (arr[(tamaño/2) – 1] + arr[tamaño/2])/2 .
A continuación se muestra la implementación del enfoque anterior: 
 

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the maximized median
float getMaxMedian(int arr[], int n, int k)
{
    int size = n + k;
 
    // Sort the array
    sort(arr, arr + n);
 
    // If size is even
    if (size % 2 == 0) {
        float median = (float)(arr[(size / 2) - 1]
                               + arr[size / 2])
                       / 2;
        return median;
    }
 
    // If size is odd
    float median = arr[size / 2];
    return median;
}
 
// Driver code
int main()
{
    int arr[] = { 3, 2, 3, 4, 2 };
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 2;
    cout << getMaxMedian(arr, n, k);
 
    return 0;
}

import java.util.*;
 
// Java implementation of the approach
class GFG
{
 
    // Function to return the maximized median
    static double getMaxMedian(int[] arr, int n, int k)
    {
        int size = n + k;
 
        // Sort the array
        Arrays.sort(arr);
 
        // If size is even
        if (size % 2 == 0)
        {
            double median = (double) (arr[(size / 2) - 1]
                    + arr[size / 2])
                    / 2;
            return median;
        }
 
        // If size is odd
        double median1 = arr[size / 2];
        return median1;
    }
 
    // Driver code
    public static void main(String[] args)
    {
        int[] arr = {3, 2, 3, 4, 2};
        int n = arr.length;
        int k = 2;
        System.out.print((int)getMaxMedian(arr, n, k));
 
    }
}
 
/* This code contributed by PrinciRaj1992 */

# Python 3 implementation of the approach
 
# Function to return the maximized median
def getMaxMedian(arr, n, k):
    size = n + k
 
    # Sort the array
    arr.sort(reverse = False)
 
    # If size is even
    if (size % 2 == 0):
        median = (arr[int(size / 2) - 1] +
                  arr[int(size / 2)]) / 2
        return median
 
    # If size is odd
    median = arr[int(size / 2)]
    return median
 
# Driver code
if __name__ == '__main__':
    arr = [3, 2, 3, 4, 2]
    n = len(arr)
    k = 2
    print(getMaxMedian(arr, n, k))
 
# This code is contributed by
# Surendra_Gangwar

// C# implementation of the approach
using System;
using System.Linq;
 
class GFG
{
     
// Function to return the maximized median
static double getMaxMedian(int []arr, int n, int k)
{
    int size = n + k;
 
    // Sort the array
    Array.Sort(arr);
 
    // If size is even
    if (size % 2 == 0)
    {
        double median = (double)(arr[(size / 2) - 1]
                            + arr[size / 2])
                    / 2;
        return median;
    }
 
    // If size is odd
    double median1 = arr[size / 2];
    return median1;
}
 
// Driver code
static void Main()
{
    int []arr = { 3, 2, 3, 4, 2 };
    int n = arr.Length;
    int k = 2;
    Console.WriteLine(getMaxMedian(arr, n, k));
}
}
 
// This code is contributed by mits

<?php
// PHP implementation of the approach
// Function to return the maximized median
function getMaxMedian($arr, $n, $k)
{
    $size = $n + $k;
 
    // Sort the array
    sort($arr, $n);
 
    // If size is even
    if ($size % 2 == 0)
    {
        $median = (float)($arr[($size / 2) - 1] +
                          $arr[$size / 2]) / 2;
        return $median;
    }
 
    // If size is odd
    $median = $arr[$size / 2];
    return $median;
}
 
// Driver code
$arr = array( 3, 2, 3, 4, 2 );
$n = sizeof($arr);
$k = 2;
echo(getMaxMedian($arr, $n, $k));
 
// This code is Contributed by Code_Mech.

<script>
 
// JavaScript implementation of the approach
 
// Function to return the maximized median
function getMaxMedian(arr, n, k) {
    let size = n + k;
 
    // Sort the array
    arr.sort((a, b) => a - b);
 
    // If size is even
    if (size % 2 == 0) {
        let median = (arr[Math.floor(size / 2) - 1] +
        arr[Math.floor(size / 2)]) / 2;
        return median;
    }
 
    // If size is odd
    let median = arr[Math.floor(size / 2)];
    return median;
}
 
// Driver code
 
let arr = [3, 2, 3, 4, 2];
let n = arr.length;
let k = 2;
document.write(getMaxMedian(arr, n, k));
 
 
// This code is contributed by _saurabh_jaiswal
 
</script>

3

Complejidad de tiempo: O(N * logN)
Espacio auxiliar: O(1)