给出一组整数作为输入。您必须返回该集合的子集，以便该子集的均值 - 中值最大值。
{1,2,3,4}
{1,2,4}
{1,2,2,3,3}
{2,2,3}
每个可能的中位数：
lllllmrrrrr
对L和R两部分进行排序，然后从两个部分开始选择对lr最大元素，并添加每个下一个元素重新计算均值，存储排列具有最佳差异。然后同样的最小元素。
关于N可能的中位数，排序需要O(N*lgN)，在每次迭代你需要计算到N意味着，你可以在O(N)做。因此，整体复杂性是O(N^3*LgN)，但很可能你可以避免在每次迭代时排序，而是只对整个数组进行一次排序，并在每次迭代时更新O(1)中的部分。有了这样的改进，它就是O(N^2)。
在O（n log n）中对列表进行排序。
删除中位数左侧的任何元素（中心元素或对）对中位数具有相同的影响，但不同地影响均值。对于右边的元素也是如此。
这意味着如果有什么改进（平均值 - 中位数），其中一个会改善它：
即，对于每个可能的新中位数，我们如何实现最大均值？
反复检查这些3-4以改善平均中位数，删除任何改善最多的东西。每个操作都是O（1），重新计算平均值和中位数。你必须在最多O（n）次这样做。
如果列表未排序，则运行时间为O（n log n），否则为O（n）。
这个问题只适用于正序数字吗？如果是的话，我写的是这段有效的代码：
import java.util.Scanner;
public class MeanMedian {
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner sc = new Scanner(System.in);
int i;
int j;
int k;
int in_length;
int mid_loc;
int sum_arr;
float median = 0.0f;
float mean = 0.0f;
float delta = 0.0f;
float incremental_delta = 0.0f;
float MEDIAN_FOR_MAX_DELTA = 0.0f;
float MEAN_FOR_MAX_DELTA = 0.0f;
float MAX_DELTA = -1.0f;
int MAX_SEQ_LENGTH = 0;
System.out.print("Enter the length of input: ");
in_length = sc.nextInt();
int in_arr[]= new int [in_length+1];
int out_arr[] = new int [in_length+1]; //This is the maximum size of the output array.
int MAX_DELTA_ARR[] = new int [in_length+1];
// STAGE-1: Accept the input sequence
for (i = 1; i <= in_length; i++) {
System.out.print("Enter the input #" + i + ": ");
in_arr[i] = sc.nextInt();
}
// STAGE-1 completed.
// STAGE-2: Sort the array (Bubble sort in Ascending order)
for (j = 1; j < in_length; j++) {
for (i = in_length; i > j; i--) {
if (in_arr[i-1] > in_arr[i]) {
k = in_arr[i];
in_arr[i] = in_arr[i-1];
in_arr[i-1] = k;
}
}
}
// STAGE-2 completed.
// STAGE-3: Compute Max Delta
MAX_DELTA = -99999; //Store as large -ve number as float data type can hold.
for (i = in_length; i > 2; i--) {
// STAGE-3a: Optional - Clear the out_arr[]
for (j = 1; j <= in_length; j++) {
out_arr [j] = 0;
}
// STAGE-3a completed.
// STAGE-3b: Determine the index of the median for the sequence of length i
if (i % 2 == 1) {
mid_loc = (i + 1)/2;
}
else {
mid_loc = (i / 2) + 1;
}
// STAGE-3b completed.
// STAGE-3c: Create the selection that gives the min median and max mean.
// STAGE-3c1: Create left side of mid point.
for (j = mid_loc; j > 0; j--) {
out_arr[j] = in_arr[j];
}
// STAGE-3c1 completed.
// STAGE-3c2: Create right side of mid point.
k = in_length;
for (j = i; j > mid_loc; j--) {
out_arr[j] = in_arr[k];
k = k - 1;
}
// STAGE-3c2 completed.
// STAGE-3c3: Do the SHIFT TEST.
//for (; k <= mid_loc + in_length - i; k++) {
for (k = mid_loc + 1; k <= mid_loc + in_length - i; k++) {
if (i % 2 == 1) {
incremental_delta = ((float)in_arr[k] - (float)out_arr[1])/i - ((float)in_arr[k] - (float)out_arr[mid_loc]);
}
else {
incremental_delta = ((float)in_arr[k] - (float)out_arr[1])/i - (((float)in_arr[k] - (float)out_arr[mid_loc]/2));
}
if (incremental_delta >= 0 ) {
//Insert this new element
for(j = 1; j < mid_loc; j++) {
out_arr[j] = out_arr[j+1];
}
out_arr[mid_loc] = in_arr[k];
}
}
// STAGE-3c3 completed.
// STAGE-3d: Find the median of the present sequence.
if(i % 2 == 1) {
median = out_arr[mid_loc];
}
else {
median = ((float)out_arr[mid_loc] + (float)out_arr[mid_loc - 1])/2;
}
// STAGE-3d completed.
// STAGE-3e: Find the mean of the present sequence.
sum_arr = 0;
for(j=1; j <= i ; j++) {
sum_arr = sum_arr + out_arr[j];
}
mean = (float)sum_arr / i;
// STAGE-3e completed.
// STAGE-3f: Find the delta for the present sequence and compare with previous MAX_DELTA. Store the result.
delta = mean - median;
if(delta > MAX_DELTA) {
MAX_DELTA = delta;
MEAN_FOR_MAX_DELTA = mean;
MEDIAN_FOR_MAX_DELTA = median;
MAX_SEQ_LENGTH = i;
for (j = 1; j <= MAX_SEQ_LENGTH; j++) {
MAX_DELTA_ARR[j] = out_arr[j];
}
}
// STAGE-3f completed.
}
// STAGE-4: Print the result.
System.out.println("--- RESULT ---");
System.out.print("The given input sequence is: ");
System.out.print("{ ");
for(i=1; i <= in_length; i++) {
System.out.print(in_arr[i]);
System.out.print(" ");
}
System.out.print("}");
System.out.println("");
System.out.print("The sequence with maximum difference between mean and median is: ");
System.out.print("{ ");
for(i=1; i <= MAX_SEQ_LENGTH; i++) {
System.out.print(MAX_DELTA_ARR[i]);
System.out.print(" ");
}
System.out.print("}");
System.out.println("");
System.out.println("The mean for this sequence is: " + MEAN_FOR_MAX_DELTA);
System.out.println("The median for this sequence is: " + MEDIAN_FOR_MAX_DELTA);
System.out.println("The maximum difference between mean and median for this sequence is: " + MAX_DELTA);
}
}
此代码具有顺序O（n）（如果我们忽略了对输入数组进行排序的必要性）。
如果 - -ve输入也是预期的 - 唯一的出路是评估每个子集。该方法的缺点是该算法具有指数阶：O（2 ^ n）。
作为折衷方案，您可以在代码中使用两种类型的算法，并通过评估输入序列在两者之间切换。顺便问一下，你在哪里遇到过这个问题？
from itertools import combinations
[Verfication of the code][1]
# function to generate all subsets possible, there will be 2^n - 1 subsets(combinations)
def subsets(arr):
temp = []
for i in range(1, len(arr)+1):
comb = combinations(arr, i)
for j in comb:
temp.append(j)
return temp
# function to calculate median
def median(arr):
mid = len(arr)//2
if(len(arr)%2==0):
median = (arr[mid] + arr[mid-1])/2
else:`
median = arr[mid]
return median
# function to calculate median
def mean(arr):
temp = 0
for i in arr:
temp = temp + i
return temp/len(arr)
# function to solve given problem
def meanMedian(arr):
sets = subsets(arr)
max_value = 0
for i in sets:
mean_median = mean(i)-median(i)
if(mean_median>max_value):
max_value = mean_median
needed_set = i
return needed_set
[1]: https://i.stack.imgur.com/Mx4pc.png
所以我尝试了一下这个问题，这里有一个可以帮助你的代码。它的编写方式应该易于阅读，如果没有，请告诉我。也许您需要从用户那里获取数组输入，因为我已经采用了固定数组。我确信这不应该是一个很大的问题。
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
class MeanMinusMedian
{
private static float mean = 0;
private static float median = 0;
private static float meanMinusMedian = 0;
private static List<Integer> meanMinusMedianList = null;
private static void formMeanMinusMedianArr(int data[], int sumOfData)
{
findMean(data, sumOfData);
findMedian(data);
if ((mean - median) > meanMinusMedian) {
meanMinusMedian = mean - median;
meanMinusMedianList = new ArrayList<Integer>();
Arrays.stream(data)
.forEach(e->meanMinusMedianList.add(e));
}
}
/**
* @param data
*/
private static void findMedian(int[] data) {
int dataLen = data.length;
median = data.length % 2 == 0 ? ((float)data[dataLen / 2] + (float)data[dataLen / 2 - 1]) / 2 : data[dataLen / 2];
}
/**
* @param data
* @param sumOfData
*/
private static void findMean(int[] data, int sumOfData) {
mean = ((float)sumOfData /(float) data.length);
}
/**
*
* @param arr
* @param data
* @param start
* @param end
* @param index
* @param runningVal
*/
private static void combinationUtil(int arr[], int data[], int start, int end, int index, int runningVal) {
// Current combination is ready to be printed, print it
if (index == runningVal) {
formMeanMinusMedianArr(data, Arrays.stream(data) // Step 1
.sum());
return;
}
// replace index with all possible elements. The condition
// "end-i+1 >= r-index" makes sure that including one element
// at index will make a combination with remaining elements
// at remaining positions
for (int i = start; i <= end && end - i + 1 >= runningVal - index; i++) {
data[index] = arr[i];
combinationUtil(arr, data, i + 1, end, index + 1, runningVal);
}
}
/**
*
* @param arr
* @param n
* @param runningVal
*/
private static void printCombination(int arr[], int n, int runningVal) {
int data[] = new int[runningVal];
// Print all combination using temporary array 'data[]'
combinationUtil(arr, data, 0, n - 1, 0, runningVal);
}
public static void main(String[] args) {
int arr[] = { 1, 2, 2, 3, 3 };
int runningVal = 1;//Running value
int len = arr.length;
for (int i = 1; i < arr.length; i++) {
printCombination(arr, len, runningVal + i);
}
System.out.println(meanMinusMedianList);
}
}