本文概述
- C ++
- Java
- Python3
- C#
例子:
输入: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)
推荐阅读
- 检查一个字符串是否可以分为两个相同的K频率字符字符串
- 数组所有子集的子集总和|O(N)
- 递归程序用给定字符串中的3.14替换所有出现的pi
- 在-1和+1数组中查找是否有大小为K的子集且总和为0
- 如何在D3.js中应用动画()
- 检查两个数字从L到R的位是否彼此互补
- 适配器模式 在Android中的简单理解
- Android屏幕信息获取
- Android应用开发中三种常见的图片压缩方法