题解 | #牛牛算数#

题意整理

给定一个数组，计算中位数和平均数。
如果中位数大于平均数，输出1；如果小于，输出-1；如果等于，输出0。

方法一（排序+模拟）

1.解题思路

首先计算中位数和平均数。
计算中位数时，先对数组排序，如果数组长度是奇数，直接返回最中间的元素；如果是偶数，则返回中间两个数的平均数。计算平均数时，先统计累加和，然后再除以数组中元素个数，即可得到平均数。
判断中位数和平均数的大小，输出对应的值。

动图展示：
图片说明

2.代码实现

import java.util.*;

public class Solution {
    /**
     * 
     * @param arr int整型一维数组 
     * @return int整型
     */
    public int Answerofjudge (int[] arr) {
        //中位数
        double median=getMedian(arr);
        //平均数
        double avg=getAvg(arr);
        //中位数大于平均数，返回1
        if(median>avg){
            return 1;
        }
        //中位数小于平均数，返回-1
        else if(median<avg){
            return -1;
        }
        //中位数等于平均数，返回0
        else{
            return 0;
        }
    }

    //计算中位数
    private double getMedian(int[] arr){
        //排序
        Arrays.sort(arr);
        int n=arr.length;
        if(n%2==1){
            return arr[n/2];
        }
        else{
            return (arr[n/2-1]+arr[n/2])/2.0;
        }
    }

    //计算平均数
    private double getAvg(int[] arr){
        int n=arr.length;
        //累加和
        double sum=0.0;
        for(int i=0;i<n;i++){
            sum+=arr[i];
        }
        return sum/n;
    }
}

3.复杂度分析

时间复杂度：排序的时间复杂度为 $O(nlog_2n)$ ，其它循环是线性的，所以时间复杂度为 $O(nlog_2n)$ 。
空间复杂度：需要额外常数级别的空间，所以空间复杂度为 $O(1)$ 。

方法二（按平均数分组）

1.解题思路

首先计算数组的平均数。
然后按平均数分为小于平均数的部分和大于等于平均数的部分。记录arr数组中小于平均数部分的最大值，大于平均数部分的最小值。
如果小于平均数的元素的数量大于 $n/2$ ，则中位数一定在小于平均数的部分取，中位数必定小于平均数，返回-1；如果小于平均数的元素的数量小于 $n/2$ ，则中位数一定在大于平均数的部分取，中位数必定大于平均数，返回1；如果小于平均数的元素的数量等于 $n/2$ ，则中位数要么取大于平均数的最小值，要么取大于平均数的最小值和小于平均数的最大值两者的平均数，然后根据情况，返回对应的值。

2.代码实现

import java.util.*;

public class Solution {
    /**
     * 
     * @param arr int整型一维数组 
     * @return int整型
     */
    public int Answerofjudge (int[] arr) {
        //平均数
        double avg=getAvg(arr);
        //num1记录arr数组中小于平均数的最大值，num2记录arr数组中大于平均数的最小值
        int num1=0,num2=Integer.MAX_VALUE;
        //cnt记录arr数组中小于平均数的个数
        int cnt=0,n=arr.length;
        for(int a:arr){
            if(a<avg){
                cnt++;
                num1=Math.max(num1,a);
            }
            else{
                num2=Math.min(num2,a);
            }
        }
        //如果小于平均数的个数有n/2个
        if(cnt==n/2){
            //如果n是奇数，则中位数恰好为num2
            if(n%2==1){
                if(avg<(double)num2) return 1;
                else if(avg>(double)num2) return -1;
                else return 0;
            }
            //如果n是偶数，则中位数为num1与num2的平均数
            else{
                if(avg<(num1+num2)/2.0) return 1;
                else if(avg>(num1+num2)/2.0) return -1;
                else return 0;
            }
        }
        return cnt>n/2?-1:1;
    }

    //计算平均数
    private double getAvg(int[] arr){
        int n=arr.length;
        //记录累加和
        double sum=0.0;
        for(int i=0;i<n;i++){
            sum+=arr[i];
        }
        return sum/n;
    }
}

3.复杂度分析

时间复杂度：所有循环都是线性的，所以时间复杂度为 $O(n)$ 。
空间复杂度：需要额外常数级别的空间，所以空间复杂度为 $O(1)$ 。