输入一个整数集合，需要返回该集合的子集，使得该子集的平均数减去中位数最大。
示例1
输入
{1,2,3,4}
输出
{1,2,4}
Example 2
Input
{1,2,2,3,3}
输出
{2,2,3}
返回一个整数子集，使其(平均值-中位数)最大化。
6
- Gaurav Kishore
4
尝试格式化你的问题以获得更好的可读性。 - Wils
1"平均数 - 中位数" 是什么意思？这些值之间有什么区别？ - MBo
从提供的例子来看，我认为这是将中位数从平均数中减去的结果。但是如果子集有偶数个元素呢？在这种情况下，中位数是否是两个中间元素的平均值？ - r3mainer
是的，平均数和中位数意味着它们的值不同。如果元素数量为偶数，则中位数将是两个中间元素的平均值。 - Gaurav Kishore
9个回答
2
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;
}
}
- Bhaskar13
8
3请添加一些细节。 - Shekhar Rai
你想要了解哪些细节？ - Bhaskar13
它正在遍历所有子集。 - Bhaskar13
@Bhaskar13 这个解决方案可以工作。但复杂度会达到2的n次方，这相当高（实际上是n乘以2的n次方，因为我们每次都要计算平均值）。你能指出如何优化这个解决方案吗？ - javaGroup456
显示剩余3条评论
1
这个问题中最重要的是找到子集。
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;
}
}
- Shubham99
1
对于每一个可能的中位数：
lllllmrrrrr
将L和R两部分排序，然后开始从两个部分中选择一对lr最大的元素，并在每次添加下一个元素时重新计算平均值，存储差异最小的排列。然后对最小元素执行相同的操作。
可能有大约N个可能的中位数，排序需要O(N*lgN)，在每次迭代中，您需要计算多达N个平均值，您可以在O(N)内完成此操作。因此，总复杂度为O(N^3*LgN)，但很可能您可以避免在每次迭代中进行排序，而是仅在整个数组上进行一次排序，并在每次迭代中以O(1)更新部分。通过这样的改进，复杂度为O(N^2)。
- Yola
1
有大约N^2/2 + N个中位数--每个列表元素都有一个，以及每对元素都有一个。 - Paul Hankin
0
这个问题只针对正数序列吗？如果是的话，我写了一段高效的代码：
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)。
如果预计会有负数输入，唯一的解决方法是评估每个子集。这种方法的缺点是算法具有指数级别的时间复杂度：O(2^n)。
作为一种折衷方案，您可以在代码中同时使用两种类型的算法，并通过评估输入序列来在两种算法之间切换。顺便问一下，你是从哪里得到这个问题的？
- Apurva Singh
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
- April
0
将列表按O(n log n)排序。
删除中位数（中心元素或对）左侧的任何元素对中位数具有相同的影响，但对平均值的影响不同。右侧的元素也是如此。
这意味着，如果有任何东西可以改善（平均值-中位数），其中之一将最大程度地改善：
- 数组中最小的元素
- 中位数右侧最小的元素
- 组成中位数的一个或多个元素
即，针对每个可能的新中位数，我们如何实现最大的平均值？
重复检查这些3-4个元素以改善平均值-中位数，删除任何最大程度改善的元素。每个操作都是O(1)，重新计算平均值和中位数也是如此。您最多需要执行O(n)次此操作。
如果列表未排序，则运行时间为O(n log n)，否则为O(n)。
- Dave
1
请您能否再详细解释一下。 - javaGroup456
0
我尝试着解决这个问题，这里有一段代码或许能帮到你。它的编写方式应该很容易阅读，如果不是，请告诉我。也许你需要从用户那里获取数组输入，就像我使用了一个固定的数组。但我相信这不会是什么大问题。
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);
}
}
- Prashant Srivastav
0
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://istack.dev59.com/Mx4pc.webp
- alpha
0
参考Bhaskar13的答案https://dev59.com/Farka4cB1Zd3GeqPh7Ul#59386801，我解决了这个问题，而不使用位移运算符，以增加可读性。
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;
}
}
- Vikash
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接