去掉最低工资和最高工资后的工资平均值


2021-01-04 简单 力扣 排序

# 题目描述

给你一个整数数组 salary ,数组里每个数都是 唯一 的,其中 salary[i] 是第 i 个员工的工资。

请你返回去掉最低工资和最高工资以后,剩下员工工资的平均值。

# 示例

输入:salary = [4000,3000,1000,2000]
输出:2500.00000
解释:最低工资和最高工资分别是 1000 和 4000 。
去掉最低工资和最高工资以后的平均工资是 (2000+3000)/2= 2500

输入:salary = [1000,2000,3000]
输出:2000.00000
解释:最低工资和最高工资分别是 1000 和 3000 。
去掉最低工资和最高工资以后的平均工资是 (2000)/1= 2000

输入:salary = [6000,5000,4000,3000,2000,1000]
输出:3500.00000

输入:salary = [8000,9000,2000,3000,6000,1000]
输出:4750.00000

输入:nums = [6]
输出:[6]

Tips:

  1. 3 <= salary.length <= 100
  2. 10^3 <= salary[i] <= 10^6
  3. salary[i] 是唯一的。
  4. 与真实值误差在 10^-5 以内的结果都将视为正确答案。

# 算法设计

这个题目并不难,只需要注意一点细节就行。其实这个题并不用排序,只需要找到最大值和最小值就行。只需要遍历一遍整个数组就可以,然而排序一般都做不到时间复杂度为O(n)。

# 代码

double average(int* salary, int salarySize){
    int max = salary[0],min = salary[0];
    double sum = 0;
    for(int i = 0;i < salarySize;i++){
        if(salary[i] > max)
            max = salary[i];
        else if(salary[i] <= min)
            min = salary[i];
        sum +=salary[i];
    }
    return ((sum - min - max) / (salarySize - 2));   
}
1
2
3
4
5
6
7
8
9
10
11
12

# 复杂度分析

时间复杂度:O(n)。选取最大值、最小值和求和的过程的时间代价都是 O(n),故渐进时间复杂度为 O(n)。

空间复杂度:O(1)。这里只用到了常量级别的辅助空间。

Last Updated: 5/13/2021, 4:48:05 PM