30分做法

用冒泡排序等方法对数组排序后找出平均数与中位数，时间复杂度o(n^2),空间复杂度o(1)

100分做法

这里提供两种做法

1.时间复杂度o(nlogn)的做法

方法同上，只是在排序中选用o(nlogn)的排序算法即可，由于相关算法众多不一一在此列举了。由于中位数和平均数都可能有精度的问题，所以这里可以比较n中位数与n平均数的大小。仅展示使用sort的做法,时间复杂度o(nlogn)，空间复杂度o(1);

class Solution {
public:
    /**
     * 
     * @param arr int整型vector 
     * @return int整型
     */
    int Answerofjudge(vector<int>& arr) {
        // write code here
        sort(arr.begin(),arr.end());
        long long sum1=0;
        long long sum2=0;
        long long n=arr.size();
        if(n%2)
        {
            sum1=arr[n/2]*n;
        }
        else
        {
            sum1=(arr[n/2]+arr[n/2-1])*n/2;
        }
        for(int i=0;i<n;i++)sum2+=arr[i];
        int ans;
        if(sum1==sum2)ans=0;
        else if(sum1>sum2)ans=1;
        else ans=-1;
        return ans;
    }
};

2.时间复杂度o(n)的做法

首先显然平均数是很容易o(n)的时间算出的，比较麻烦的就是中位数，因为中位数只和最中间的一个/两个数有关，所以可以用黑科技nth_element()在数据大时可以o(n)的时间复杂度找到中位数。空间复杂度o(1)。（虽然理论时间复杂度是低的，但是常数较大再加上sort的log的常数很小，实际测试时两者运行时间差别并不明显，特此说明）代码如下：

class Solution {
public:
    /**
     * 
     * @param arr int整型vector 
     * @return int整型
     */
    int Answerofjudge(vector<int>& arr) {
        // write code here
        long long sum1=0;
        long long sum2=0;
        long long n=arr.size();
        if(n%2)
        {
            nth_element(arr.begin(),arr.begin()+n/2+1,arr.end());
            sum1=arr[n/2]*n;
        }
        else
        {
            nth_element(arr.begin(),arr.begin()+n/2,arr.end());
            sum1=arr[n/2];
            nth_element(arr.begin(),arr.begin()+n/2-1,arr.end());
            sum1+=arr[n/2-1];
            sum1*=n/2;
        }
        for(int i=0;i<n;i++)sum2+=arr[i];
        int ans;
        if(sum1==sum2)ans=0;
        else if(sum1>sum2)ans=1;
        else ans=-1;
        return ans;
    }
};