Mediana después de K enteros adicionales

Dada una array de n enteros. Se nos permite agregar k enteros adicionales en la array y luego encontrar la mediana de la array resultante. Podemos elegir cualquier valor de k para agregar. 
Restricciones: 
 

k < n
n + k is always odd.

Ejemplos: 
 

Input : arr[] = { 4, 7 }
         k = 1 
Output : 7
Explanation : One of the possible solutions 
is to add 8 making the array [4, 7, 8], whose
median is 7

Input : arr[] = { 6, 1, 1, 1, 1 }
         k = 2
Output : 1
Explanation : No matter what elements we add 
to this array, the median will always be 1

Primero ordenamos la array en orden creciente. Dado que el valor de k es menor que n y n+k siempre es impar, siempre podemos optar por agregar k elementos que sean mayores que el elemento más grande de una array, y (n+k)/2º elemento siempre es una mediana de la formación. 
 

// CPP program to find median of an array when
// we are allowed to add additional K integers
// to it.
#include <bits/stdc++.h>
using namespace std;
 
// Find median of array after adding k elements
void printMedian(int arr[], int n, int K)
{
    // sorting  the array in increasing order.
    sort(arr, arr + n);
 
    // printing the median of array.
    // Since n + K is always odd and K < n,
    // so median of array always lies in
    // the range of n.
    cout << arr[(n + K) / 2];
}
 
// driver function
int main()
{
    int arr[] = { 5, 3, 2, 8 };
    int k = 3;
    int n = sizeof(arr) / sizeof(arr[0]);
    printMedian(arr, n, k);
    return 0;
}

// Java program to find median of an array when
// we are allowed to add additional K integers
// to it.
import java.util.Arrays;
 
class GFG {
     
    // Find median of array after adding k elements
    static void printMedian(int arr[], int n, int K)
    {
         
        // sorting the array in increasing order.
        Arrays.sort(arr);
     
        // printing the median of array.
        // Since n + K is always odd and K < n,
        // so median of array always lies in
        // the range of n.
        System.out.print(arr[(n + K) / 2]);
    }
     
    //Driver code
    public static void main (String[] args)
    {
         
        int arr[] = { 5, 3, 2, 8 };
        int k = 3;
        int n = arr.length;
         
        printMedian(arr, n, k);
    }
}
 
// This code is contributed by Anant Agarwal.

# Python3 code to find median of an
# array when we are allowed to add
# additional K integers to it.
 
# Find median of array after
# adding k elements
def printMedian (arr, n, K):
     
    # sorting the array in
    # increasing order.
    arr.sort()
     
    # printing the median of array.
    # Since n + K is always odd
    # and K < n, so median of
    # array always lies in
    # the range of n.
    print( arr[int((n + K) / 2)])
 
# driver function
arr = [ 5, 3, 2, 8 ]
k = 3
n = len(arr)
printMedian(arr, n, k)
 
# This code is contributed by "Sharad_Bhardwaj".

// C# program to find median of an array when
// we are allowed to add additional K integers
// to it.
using System;
 
class GFG
{
    // Find median of array after adding k elements
    static void printMedian(int []arr, int n, int K)
    {
        // sorting  the array in increasing order.
        Array.Sort(arr);
      
        // printing the median of array.
        // Since n + K is always odd and K < n,
        // so median of array always lies in
        // the range of n.
        Console.Write(arr[(n + K) / 2]);
    }
     
    //Driver code
    public static void Main ()
    {
    int []arr = { 5, 3, 2, 8 };
        int k = 3;
        int n = arr.Length;
        printMedian(arr, n, k);
    }
}
 
// This code is contributed by  anant321.

<?php
// PHP program to find median
// of an array when we are allowed
// to add additional K integers to it.
 
// Find median of array
// after adding k elements
function printMedian($arr, $n, $K)
{
    // sorting the array
    // in increasing order.
    sort($arr);
 
    // printing the median of
    // array. Since n + K is
    // always odd and K < n,
    // so median of array always
    // lies in the range of n.
    echo $arr[($n + $K) / 2];
}
 
// Driver Code
$arr = array( 5, 3, 2, 8 );
$k = 3;
$n = count($arr);
printMedian($arr, $n, $k);
 
// This code is contributed by Sam007
?>

<script>
 
// Javascript program to find median of an array when
// we are allowed to add additional K integers
// to it.
 
    // Find median of array after adding k elements
    function printMedian(arr, n, K)
    {
           
        // sorting the array in increasing order.
        arr.sort();
       
        // printing the median of array.
        // Since n + K is always odd and K < n,
        // so median of array always lies in
        // the range of n.
        document.write(arr[Math.floor((n + K) / 2)]);
    }
 
// driver program
 
        let arr = [ 5, 3, 2, 8 ];
        let k = 3;
        let n = arr.length;
           
        printMedian(arr, n, k);
             
</script>

Producción :  

8

Complejidad temporal: O(nlog(n))
Espacio auxiliar: O(1)
Este artículo es una contribución de Saloni Gupta . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.