Divida la array en dos grupos de longitud impar con una diferencia absoluta minimizada entre su mediana

Dada una array arr[] de enteros positivos de longitud par, la tarea es dividir estos elementos de arr[] en dos grupos, cada uno de longitud impar, de modo que se minimice la diferencia absoluta entre la mediana de los dos grupos.
Ejemplos: 
 

Entrada: arr[] = { 1, 2, 3, 4, 5, 6 } 
Salida: 1 
Explicación: 
El grupo 1 puede ser [2, 4, 6] con mediana 4 
El grupo 2 puede ser [1, 3, 5] con mediana 3. 
La diferencia absoluta entre las dos medianas es 4 – 3 = 1, que no se puede minimizar más con ningún tipo de agrupación formada.
Entrada: arr[] = { 15, 25, 35, 50 } 
Salida: 10 
Explicación: 
El grupo 1 puede ser [15, 25, 50] con mediana 25 
El grupo 2 puede ser [35] con mediana 35. 
La diferencia absoluta entre el dos medianas es 35 – 25 = 10, que no se puede minimizar más con ningún tipo de agrupación formada. 
 

Acercarse: 
 

• Si se ordena la array dada arr[] , los elementos intermedios de arr[] darán la diferencia mínima.
• Entonces divida el arr[] de tal manera que estos dos elementos sean la mediana de dos nuevos arreglos de longitud impar.
• Por lo tanto, coloque el n/2 elemento del arr[] en el primer grupo y el ⁽ n/2 – 1) elemento del ^arr [] en el segundo grupo como mediana respectivamente.
• Entonces abs(arr[n/2] – arr[(n/2)-1]) es la diferencia mínima entre las dos nuevas arrays.

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

// C++ program to minimize the
// median between partition array
 
#include "bits/stdc++.h"
using namespace std;
 
// Function to find minimize the
// median between partition array
int minimizeMedian(int arr[], int n)
{
    // Sort the given array arr[]
    sort(arr, arr + n);
 
    // Return the difference of two
    // middle element of the arr[]
    return abs(arr[n / 2] - arr[(n / 2) - 1]);
}
 
// Driver Code
int main()
{
    int arr[] = { 15, 25, 35, 50 };
 
    // Size of arr[]
    int n = sizeof(arr) / sizeof(arr[0]);
 
    // Function that returns the minimum
    // the absolute difference between
    // median of partition array
    cout << minimizeMedian(arr, n);
    return 0;
}

// Java program to minimise the
// median between partition array
import java.util.*;
 
class GFG
{
 
    // Function to find minimise the
    // median between partition array
    static int minimiseMedian(int arr[], int n)
    {
        // Sort the given array arr[]
        Arrays.sort(arr);
     
        // Return the difference of two
        // middle element of the arr[]
        return Math.abs(arr[n / 2] - arr[(n / 2) - 1]);
    }
     
    // Driver Code
    public static void main (String[] args)
    {
        int arr[] = { 15, 25, 35, 50 };
     
        // Size of arr[]
        int n = arr.length;
     
        // Function that returns the minimum
        // the absolute difference between
        // median of partition array
        System.out.println(minimiseMedian(arr, n));
    }
}
 
// This code is contributed by AnkitRai01

# Python3 program to minimise the
# median between partition array
 
# Function to find minimise the
# median between partition array
def minimiseMedian(arr, n) :
 
    # Sort the given array arr[]
    arr.sort();
     
    # Return the difference of two
    # middle element of the arr[]
    ans = abs(arr[n // 2] - arr[(n // 2) - 1]);
     
    return ans;
 
# Driver Code
if __name__ == "__main__" :
 
    arr = [ 15, 25, 35, 50 ];
 
    # Size of arr[]
    n = len(arr);
 
    # Function that returns the minimum
    # the absolute difference between
    # median of partition array
    print(minimiseMedian(arr, n));
     
# This code is contributed by AnkitRai01

// C# program to minimise the
// median between partition array
using System;
 
class GFG
{
 
    // Function to find minimise the
    // median between partition array
    static int minimiseMedian(int []arr, int n)
    {
        // Sort the given array []arr
        Array.Sort(arr);
     
        // Return the difference of two
        // middle element of the []arr
        return Math.Abs(arr[n / 2] - arr[(n / 2) - 1]);
    }
     
    // Driver Code
    public static void Main(String[] args)
    {
        int []arr = { 15, 25, 35, 50 };
     
        // Size of []arr
        int n = arr.Length;
     
        // Function that returns the minimum
        // the absolute difference between
        // median of partition array
        Console.WriteLine(minimiseMedian(arr, n));
    }
}
 
// This code is contributed by 29AjayKumar

<script>
 
// JavaScript program to minimise the
// median between partition array
 
// Function to find minimise the
// median between partition array
function minimiseMedian(arr, n) {
    // Sort the given array arr[]
    arr.sort((a, b) => a - b);
 
    // Return the difference of two
    // middle element of the arr[]
    return Math.abs(arr[n / 2] - arr[(n / 2) - 1]);
}
 
// Driver Code
let arr = [15, 25, 35, 50];
 
// Size of arr[]
let n = arr.length;
 
// Function that returns the minimum
// the absolute difference between
// median of partition array
document.write(minimiseMedian(arr, n));
 
// This code is contributed by gfgking
 
</script>

10

Complejidad de tiempo: O(N*log N)