去掉最低工资和最高工资后的工资平均值
shinuye 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:
- 3 <= salary.length <= 100
- 10^3 <= salary[i] <= 10^6
- salary[i] 是唯一的。
- 与真实值误差在 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
2
3
4
5
6
7
8
9
10
11
12
# 复杂度分析
时间复杂度：O(n)。选取最大值、最小值和求和的过程的时间代价都是 O(n)，故渐进时间复杂度为 O(n)。
空间复杂度：O(1)。这里只用到了常量级别的辅助空间。