一组
整数作为输入。您必须返回该集合的子集，以便该子集的均值 - 中位数为最大值。
例 1
输入
{1,2,3,4}
输出
{1,2,4}
例 2
输入
{1,2,2,3,3}
输出
{2,2,3}
package subsetMean_Median;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class MySolution {
public static void main(String[] args) {
int[] arr=
{2,3,2,1,3};
// {1,3,2,4};
Arrays.sort(arr);
int[] outp=meanMedian(arr);
for(int e:outp) {
System.out.print(e+"t");
}
}
protected static int[] meanMedian(int[] arr) {
double median=findMedian(arr);
double mean=findMean(arr);
double diff=median-mean;
int MAXINDEX=0;
int n=arr.length;
double sets=(1<<n);
System.out.println("sets:"+sets);
for(int i=1;i<=sets;i++) {
int[] subset=findSubset(i,arr);
mean=findMean(subset);
median=findMedian(subset);
if(mean -median>diff) {
diff=mean-median;MAXINDEX=i;
}
}
System.out.println("mean: "+mean+"tmedian: "+median+"tdiff: "+diff);
return findSubset(MAXINDEX,arr);
}
protected static int[] findSubset(int counter, int[] arr) {
int n=arr.length;
List<Integer> ls=new ArrayList<Integer>();
for(int j=0;j<n;j++) {
if((counter & (1<<j))>0) {
ls.add(arr[j]);
}
}
int[] output= new int[ls.size()];
for(int j=0;j<ls.size();j++) {
output[j]=ls.get(j);
}
return output;
}
protected static double findMean(int[] arr) {
int n=arr.length;
double sum=0;
if(n==0) return 0;
for(int i=0;i<n;i++)
sum +=arr[i];
return (sum/n);
}
protected static double findMedian(int[] arr) {
int n=arr.length;
if(n%2==1)
return arr[(n/2)];
else if(n>=2)
return 0.5*(arr[((n-2)/2)]+arr[n/2]);
else return 0;
}
}
对于每个可能的中位数：
lllllmrrrrr
对部分 L 和 R 进行排序，然后开始从两个部分中成对选择lr最大元素，并添加每个下一个元素重新计算平均值，存储具有最佳差异的排列。然后对于最小元素也是如此。
大约有 N 个可能的中位数，排序需要O(N*lgN)，在每次迭代中，您需要计算多达 N 个平均值，您可以在 O(N) 中完成。因此，整体复杂性是O(N^3*LgN)，但最有可能的是，您可以避免对每次迭代进行排序，而是只对整个数组进行一次排序，并在每次迭代时O(1)更新部分。有了这样的改进，它O(N^2).
这个问题中最重要的是找到子集。
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class MeanMedian {
public static void main(String[] args) {
int[] arr = { 1, 2, 3 };// { 1, 2, 2, 3, 3 };// { 1, 2, 3, 4 };
returnMaxMeanMedian(arr);
}
private static void returnMaxMeanMedian(int[] arr) {
double max = -999.9;
List<Integer[]> subArr = subSet(arr);
Integer[] maxArr = new Integer[1];
for (Integer[] sub : subArr) {
double newMax = calcDiff(sub);
if (max <= newMax) {
max = newMax;
maxArr = sub;
}
}
System.out.println(Arrays.toString(maxArr));
}
private static double calcDiff(Integer[] sub) {
// calc. mean
double sum = 0;
for (int i = 0; i < sub.length; i++) {
sum += sub[i];
}
sum = sum / sub.length;
// calc. median
double median = 0;
if (sub.length % 2 == 0)
median = (double) (sub[(sub.length / 2) - 1] + sub[sub.length / 2]) / 2;
else
median = sub[sub.length / 2];
double diff = sum - median;
return diff;
}
private static List<Integer[]> subSet(int[] arr) {
List<Integer[]> subArr = new ArrayList<Integer[]>();
int n = arr.length;
// Run a loop until 2^n
// subsets one by one
for (int i = 0; i < (1 << n); i++) {
String subSet = "";
// Print current subset
for (int j = 0; j < n; j++)
if ((i & (1 << j)) > 0)
subSet += arr[j] + " ";
subArr.add(convertToInt(subSet.trim().split(" ")));
}
return subArr;
}
private static Integer[] convertToInt(String[] arr) {
if (arr[0] == "")
return new Integer[] { 0 };
Integer[] intArr = new Integer[arr.length];
for (int i = 0; i < arr.length; i++) {
intArr[i] = Integer.parseInt(arr[i].trim());
}
return intArr;
}
}
在 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);
}
}
参考 Bhaskar13 https://stackoverflow.com/a/59386801/3509609 的答案，我在不使用位移运算符的情况下解决了它，以增加更多的可读性。
package array;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.Map;
public class MeanMinusMedianMax {
public static void main(String[] args) {
System.out.println(Arrays.toString(maxDiffrenceSubSet(4, new int[] { 4, 2, 3, 1 })));
System.out.println(Arrays.toString(maxDiffrenceSubSet(4, new int[] { 1, 2, 2, 3, 3 })));
}
public static int[] maxDiffrenceSubSet(int n, int[] input2) {
int totalSubsets = (int) Math.pow(2, n);
Map<Integer, ArrayList<Integer>> subsetsMap = new HashMap<Integer, ArrayList<Integer>>();
Integer maxKey = null;
double maxDiff = 0;
for (int i = 0; i < totalSubsets; i++) {
String binaryString = Integer.toBinaryString(i);
while (binaryString.length() < 4) {
binaryString = "0" + binaryString;
}
char[] currentPick = binaryString.toCharArray();
ArrayList<Integer> currentList = new ArrayList<Integer>();
for (int x = 0; x < currentPick.length; x++) {
if ((currentPick[x]) == '1') {
currentList.add(input2[x]);
}
}
Collections.sort(currentList);
subsetsMap.put(i, currentList);
double mean = findMean(currentList);
double median = findMedian(currentList);
double currentDifference = mean - median;
if (currentDifference > maxDiff) {
maxDiff = currentDifference;
maxKey = i;
}
}
return subsetsMap.get(maxKey).stream().mapToInt(i -> i).toArray();
}
static double findMean(ArrayList<Integer> arr) {
int n = arr.size();
double sum = 0;
if (n == 0)
return 0;
for (int i = 0; i < n; i++)
sum += arr.get(i);
return (sum / n);
}
static double findMedian(ArrayList<Integer> arr) {
int n = arr.size();
if (n % 2 == 1)
return arr.get((n / 2));
else if (n >= 2)
return 0.5 * (arr.get(((n - 2) / 2)) + arr.get(n / 2));
else
return 0;
}
}
class UserMainCode (object):
def meanmedian(cls,ip1,ip2=[]):
s = []
s = ip2
lst = []
final = []
op = []
max_val = 0
diff = 0
for i in range(1,ip1+1):
n=i
lst = list(itertools.combinations(s,n))
final = final +lst
for i in range(len(final)):
men = statistics.mean(final[i])
med = statistics.median(final[i])
diff = men - med
if max_val < diff:
op = final[i]
max_val = diff
return op