题解 | #牛牛算数#

牛牛算数

http://www.nowcoder.com/practice/2470140c86c6480796a487f79cf8df3a

NC637 牛牛算数

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

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

方法一: 模拟

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

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) 只使用若干个变量

全部评论

相关推荐

不愿透露姓名的神秘牛友
昨天 12:11
我最近都有点不想活了,天天早10晚11的,还问我爱不爱她目前的状态别说爱谁了,没扇谁就不错了。是不是大家都是一进节子,只有工作没有爱情了
AzureSkies:在字节的时候找的就是字节的,飞书太适合恋爱人士了,能看到是不是已读,是不是在会议中。简直冥婚好伴侣
投递字节跳动等公司9个岗位
点赞 评论 收藏
分享
代码飞升:别用口语,后端就写后端,前端就写前端,最后别光后悔
点赞 评论 收藏
分享
nus2201602...:兄弟,你这个简历撕了丢了吧,就是一坨,去找几个项目,理解项目流程,看几遍就是你的了,看看八股就去干了,多看看牛客里别人发出来的简历,对着写,你这写的啥啊,纯一坨
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务