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

本文概述

  • 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)

    推荐阅读