题解 | #牛牛算数#

一.题目描述

NC637牛牛算数

给出n个元素的数组arr[i]，问这个数组的中位数大还是平均数大，如果中位数更大输出1，如果平均数更大输出-1，如果中位数和平均数相等输出0。

二.算法一(模拟)

对于比较最后中位数和平均数的大小，我们可以直接求出来整个数列的中位数和平均数，如果中位数更大返回1，如果平均数更大返回-1，如果 中位数和平均数相等返回0。下面是完整代码：

class Solution {
public:
    int Answerofjudge(vector<int>& arr) {
        double ave=0;
        int num=arr.size();
        sort(arr.begin(),arr.end());//对数列进行排序
        double mid;//表示最后的中位数
        //对于数列个数的奇数还是偶数分情况求出中位数
        if(arr.size()%2==0){
            int a=num/2;
            int b=a-1;//由于是vector所以下标要减去1
            mid=1.0*(arr[a]+arr[b])/2.0;
        } else{
            mid=arr[num/2];
        }
        for(int i=0;i<num;i++){
            ave+=arr[i];
        }
        ave/=num;//计算出平均值
        if(mid>ave){
            return 1;
        } else if(mid==ave){
            return 0;
        } else {
            return -1;
        }
    }
};

时间复杂度：$O(nlogn)O(nlogn)$虽然整个过程只需要对数列进行一次遍历，但是需要对数组进行排序，所以时间复杂度是$O(nlogn)O(nlogn)$

空间复杂度：$O(1)O(1)$不需要额外的空间

三.算法二(+一个小技巧)

前面的算法一需要我们对数列进行一次排序时间复杂度比较高，我们可以想到中位数的值只是和中间的那个两个数或者一个数有关，所以我们只是需要找到中间那个一个数或者两个数就可以求出中位数了。如何求出中间的数呢？我们可以利用平均值求出来，我们可以记录比平均数小的数字个数，同时找到比平均值大于的最小数和比平均值小于的最大数，若记录比平均数小的个数不等于数组长度的一半，那么平均值和中位数一定不会相等，所以只需要比较是大于数组长度的一般还是小于，返回-1还是1；要是等于数组长度的一半，那么就可以分奇数和偶数来比较中位数和平均数的大小，下面是完整代码：

class Solution {
public:
    /**
     * 
     * @param arr int整型vector 
     * @return int整型
     */
    int Answerofjudge(vector<int>& arr) {
        int len=arr.size();
        double sum=0;
        for(int i=0;i<len;i++){
            sum+=arr[i];
        }
        double av=1.0*sum/len;
        int l=0,r=1e9+7;//l,r分别表示比平均数大的最小值和平均数小的最大值
        int cn=0;//记录小于平均数的个数
        for(int i=0;i<len;i++){
            if(arr[i]<av){
                l=max(l,arr[i]);
                cn++;
            } else {
                r=min(r,arr[i]);
            }
        }
        if(cn==len/2){
            //分奇数和偶数判断
            if(len%2==0){
                if(av<1.0*(l+r)/2.0) return 1;
                else if(av==1.0*(l+r)/2.0) return 0;
                else return -1;
            } else {
                if(av<1.0*r) return 1;
                else if(av==1.0*r) return 0;
                else return -1;
            }
            
        } else {
            if(cn> len/2){
                return -1;
            } else {
                return 1;
            }
        }
    }
};

时间复杂度：$O(n)O(n)$虽然整个过程只需要对数列进行两次次遍历，时间复杂度比较低。

空间复杂度：$O(1)O(1)$不需要额外的空间