Easy

题目描述

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

请你返回去掉最低工资和最高工资以后，剩下员工工资的平均值。与标准答案误差在 10^-5 以内的结果都将视为正确答案。

示例 1：

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

示例 2：

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

提示：

  • 3 <= salary.length <= 100
  • 1000 <= salary[i] <= 10^6
  • salary 中的所有整数都是 唯一 的

解题思路

这道题目要求计算去掉最低和最高工资后的平均值，思路非常直观。

方法一：一次遍历（推荐）

  • 在一次遍历中同时计算总和、最小值和最大值
  • 最后用 (总和 - 最小值 - 最大值) / (数组长度 - 2) 得到结果
  • 时间复杂度 O(n)，空间复杂度 O(1)，效率最高

方法二：排序法

  • 对数组进行排序，然后计算中间元素的平均值
  • 虽然思路简单，但时间复杂度为 O(n log n)，不如方法一高效

方法三：先求和再找极值

  • 先遍历一次求总和，再遍历一次找最值
  • 需要遍历两次，虽然时间复杂度仍为 O(n)，但常数因子较大

由于数组保证有唯一元素且长度至少为3，不需要处理边界情况。推荐使用方法一，代码简洁且效率最高。

代码实现

class Solution {
public:
    double average(vector<int>& salary) {
        int minSal = salary[0], maxSal = salary[0];
        int sum = 0;
        
        for (int sal : salary) {
            sum += sal;
            minSal = min(minSal, sal);
            maxSal = max(maxSal, sal);
        }
        
        return (double)(sum - minSal - maxSal) / (salary.size() - 2);
    }
};

class Solution:
    def average(self, salary: List[int]) -> float:
        min_sal = max_sal = salary[0]
        total = 0
        
        for sal in salary:
            total += sal
            min_sal = min(min_sal, sal)
            max_sal = max(max_sal, sal)
        
        return (total - min_sal - max_sal) / (len(salary) - 2)

public class Solution {
    public double Average(int[] salary) {
        int minSal = salary[0], maxSal = salary[0];
        int sum = 0;
        
        foreach (int sal in salary) {
            sum += sal;
            minSal = Math.Min(minSal, sal);
            maxSal = Math.Max(maxSal, sal);
        }
        
        return (double)(sum - minSal - maxSal) / (salary.Length - 2);
    }
}

var average = function(salary) {
    let minSal = salary[0], maxSal = salary[0];
    let sum = 0;
    
    for (let sal of salary) {
        sum += sal;
        minSal = Math.min(minSal, sal);
        maxSal = Math.max(maxSal, sal);
    }
    
    return (sum - minSal - maxSal) / (salary.length - 2);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型大小
时间复杂度O(n)
空间复杂度O(1)