将数组分成两个奇数长度的组，中间值之间的绝对差最小

本文概述

• C ++
• Java
• Python3
• C#

给定一个数组arr []长度为偶数的正整数, 任务是对arr []分成两组, 每个组的长度都奇数, 以使两组中位数之间的绝对差最小。

例子：

输入：arr [] = {1, 2, 3, 4, 5, 6}
输出：1
说明：组1可以是[2, 4, 6], 中位数4组2可以是[1, 3, 5]中位数3。两个中位数之间的绝对差为4 – 3 = 1, 使用任何形式的分组都无法进一步将其最小化。
输入：arr [] = {15, 25, 35, 50}
输出：10
说明：组1可以是[15、25、50], 中位数为25组2可以是[35], 中位数35。两个中位数是35 – 25 = 10, 使用任何形式的分组都无法进一步将其最小化。

方法：

• 如果给定数组arr []被排序, 中间的元素arr []将给出最小的差异。
• 所以划分arr []这样, 这两个元素将成为两个新的奇数长度数组的中值。
• 因此, 将n / 2th第一组中arr []的元素和(n / 2 – 1)th的元素arr []第二组分别作为中位数。
• 然后abs(arr [n / 2] – arr [(n / 2)-1])是两个新数组之间的最小差。

下面是上述方法的实现：

C ++

//C++ program to minimise the
//median between partition array
  
#include "bits/stdc++.h"
using namespace std;
  
//Function to find minimise the
//median between partition array
int minimiseMedian( 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 <<minimiseMedian(arr, n);
     return 0;
}

Java

//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

# 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#

//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

输出如下：

10

时间复杂度：O(N * log N)

---