题目描述

给定一个整数数组 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

限制

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

算法

(一次线性遍历) $O(n)$

1. 仅遍历数组一次。初始化两个变量 mi 为前两个元素中的最小值和 ma 为前两个元素中的最大值，总和 tot 初始化为 0。
2. 从第三个元素开始遍历数组，如果 mi 大于当前元素，则令 tot 加上之前的 mi，然后更新 mi，否则如果 ma 小于当前元素，则令 tot 加上之前的 ma，然后更新 ma。否则，tot 加上当前元素。
3. 最后求平均值。

时间复杂度

• 仅遍历数组一次，故时间复杂度为 $O(n)$。

空间复杂度

• 仅需要常数的额外空间。

C++ 代码

class Solution {
public:
    double average(vector<int>& salary) {
        int mi, ma;
        mi = salary[0]; ma = salary[1];
        if (mi > ma) swap(mi, ma);

        int tot = 0;
        for (int i = 2; i < salary.size(); i++)
            if (mi > salary[i]) {
                tot += mi;
                mi = salary[i];
            } else if (ma < salary[i]) {
                tot += ma;
                ma = salary[i];
            } else {
                tot += salary[i];
            }

        return 1.0 * tot / (salary.size() - 2);
    }
};