NC637 牛牛算数

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

案例
输入：[6,6,6,6,5,8]
返回值：-1
说明：中位数6，平均数约等于6.17，所以输出-1

方法一: 模拟

对原先的序列进行排序,如果n为偶数取正中间的两位做中位数也就是$(n\mathrm{/}2\mathrm{和}n\mathrm{/}2-1)(n\; /\; 2\; 和\; n\; /\; 2\; -\; 1)$位，如果n位奇数则中位数为$(n\mathrm{/}2)(n\; /\; 2)$.然后在遍历一遍求平均数做对比即可

class Solution {
public:
    /**
     * 
     * @param arr int整型vector 
     * @return int整型
     */
    int Answerofjudge(vector<int>& arr) {
        // write code here
        sort(arr.begin(), arr.end()); //从小到大排序
        int n = arr.size();
        double sum = 0, cen = 0;
        for(int i = 0; i < n; i ++){
            sum += arr[i];
        }
        if(n % 2){//如果n是记述直接取中间的
            if(arr[n / 2] == 1.0 * sum / n) return 0; 
            if(arr[n / 2] >= 1.0 * sum / n) return 1;
            return -1;
        }
        cen = (arr[n / 2] + arr[n / 2 - 1]) / 2.0; //中间的两位
        if(cen == 1.0 * sum / n) return 0;
        if(cen >= 1.0 * sum / n) return 1;
        return -1;
    }
};

时间复杂度: $O(nlogn)O(nlogn)$ 排序一遍所需要的时间
空间复杂度: $O(1)O(1)$ 只使用若干个变量

方法二: 前缀和

对序列进行一个排序，并做前缀和预处理，后平均数为前缀和第n位的值/n，中位数需要判断一下n是奇数还是偶数与方法一一致

class Solution {
public:
    /**
     * 
     * @param arr int整型vector 
     * @return int整型
     */
    long long d[1000010];
    int Answerofjudge(vector<int>& arr) {
        // write code here
        sort(arr.begin(), arr.end()); //从小到大排序
        int n = arr.size();
        double sum = 0, cen = 0;
        d[0] = arr[0];
        for(int i = 1; i < n; i ++){ //记录前缀和
            d[i] = d[i - 1] + arr[i];
        }
        sum = 1.0 * d[n - 1] / (1.0 * n);
        if(n % 2 == 0){//如果n是记述直接取中间的
             cen = (d[n / 2] - d[n / 2 - 2]) / 2.0; //中间的两位
        }else cen = d[n / 2] - d[n / 2 - 1];
        if(cen == sum) return 0;
        if(cen >= sum) return 1;
        return -1;
    }
};

时间复杂度: $O(nlogn)O(nlogn)$ 排序一般所需要的复杂度
空间复杂度: $O(1)O(1)$ 只使用若干个变量