竞争性编程中的平均中位数模式问题

Question

我在一次公司入学考试中得到了以下问题。除4个测试用例外，所有测试用例均通过。有没有人能试着找出可能出现的情况，哪些可能会失败。问题和解决方案如下：

均值、中位数和模式

给定n个整数，求其平均中值和模式。您需要填写一个接受输入整数“input1”（1）的函数

平均数和中位数必须正确到小数点后六位。

平均值：定义为数组中所有数字的平均值。

中位数：定义为数组的中间元素。

如果n是偶数，则中值是两个中间元素的平均值；如果n是奇数，则中值是数组的中间元素。

注意：为了找到中位数，数组中的元素必须按从小到大的数字顺序列出。

模式：定义为数组中频率最高的数字。如果许多数字具有相同的最高频率，则通过打破有利于最小数字的联系来计算模式。

输入规格：

Input1：范围为1的整数

Input2：整数输入数组。

输出规格：

返回output1（double）变量作为平均值。

返回output2（double）变量作为中位数。

返回output3（int）变量作为模式。

样本测试案例1：

输入1:3

输入2：{1,2,3}

产出：2.000000,2.000000,1

样本测试案例2：

输入1:5

输入2：{41, 18467, 6334, 26500, 19169}

产量：14102.20000018467.00000041

package algo;
import java.util.*;

public class MeanMedianMode 
{
    // Functhtml" target="_blank">ion for calculating mean
    public static double findMean(int n , int a[])
    {
        int sum = 0;
        for (int i = 0; i < n; i++)

        sum += a[i];

    return (double)sum / (double)n;
}

public static double findMedian(int n, int a[])
{
    // First we sort the array
    Arrays.sort(a);

    // check for even case
    if (n % 2 != 0)
        return (double)a[n / 2];

    return (double)(a[(n - 1) / 2] + a[n / 2]) / 2.0;
}

public static int findMode(int n, int a[] ) {
    int maxValue=0, maxCount=0;

    for (int i = 0; i < a.length; ++i) {
        int count = 0;
        for (int j = 0; j < a.length; ++j) {
            if (a[j] == a[i]) ++count;
        }
        if (count >  maxCount) {
            maxCount = count;
            maxValue = a[i];
        }
    }

   return maxValue;
 }

// Driver code
public static void main(String args[])
{
    int a[] = { 41, 18467, 6334, 26500, 19169 };
    int n = a.length;

    System.out.println("Mean = " + String.format("%.6f", findMean(n, a)));
    System.out.println("Median = " + String.format("%.6f", findMedian(n, a)) );
    System.out.println("Mode = " + findMode(n, a));
}
}

编辑：有没有双模、三模数组的场景，比如{1,1,2,2}和{1,1,2,2,3,3}，其中模式可以是{1,2}或{1,2,3}。我问这个问题是因为在这种情况下，返回类型将是int[]，但有一个问题特别提到，返回类型必须是int。

Answer 1

问题出现在findMode中。你不能处理多个数字具有相同最高频率的情况。问题陈述说：

如果许多数字具有相同的最高频率，则通过打破有利于最小数字的联系来计算模式。

最简单的解决方案是仅当模式值低于先前的模式值时才存储模式值——将模式值初始化为可能的最高值。

public static int findMode(int n, int a[] ) {
    int maxValue = Integer.MAX_VALUE; // Note that a[0]+1 would also work
    int maxCount = 0;
    
    for (int i = 0; i < a.length; ++i) {
        int count = 0;
        for (int j = 0; j < a.length; ++j) {
            if (a[j] == a[i]) ++count;
        }
        if (count >= maxCount && a[i] < maxValue) {
            maxCount = count;
            maxValue = a[i];
        }
    }
    
    return maxValue;
}

请注意，您的算法效率低下，因为它每次出现在列表中都会计算相同的数字。例如，如果1在列表中出现100次，它将计算1的频率100次。

编辑：好的，因为您对数组进行了排序，所以这不是问题所在。

我能想到的另一件事是，findMean中有整数溢出。int可容纳的最大值为2147483647。由于数组可能很大（最多1000个元素），所以很可能int sum无法保存该值。尝试更改为double sum=0