夯实算法-去掉最低工资和最高工资后的工资平均值

题目：LeetCode

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

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

示例 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 = [6000,5000,4000,3000,2000,1000]
输出： 3500.00000

示例 4：

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

提示：

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

解题思路

解法一

• ①：先排序
• ②：遍历时从第二个元素开始，倒数第二个元素结束，即排除了最小值和最大值，遍历过程中进行累加
• ③：累加的结果除以元素总个数-2

解法二

将数组排序，调用sort方法，然后记录去除最小和最大值得个数，然后将剩余的人工资进行累加 最后进行求平均值。

代码实现

解法一

public double average(int[] salary) {
   Arrays.sort(salary);
   double sum = 0;
   for(int i = 1; i < (salary.length - 1 ); i++){
    sum += salary[i];
   }
   return sum/(salary.length - 2);
}

解法二

public double average(int[] salary) {
     Arrays.sort(salary);
     int count=salary.length-2;
     int b=0;
     for(int i=1;i<salary.length-1;i++){
       b+=salary[i];
     }
    return b/(double)count;
}

复杂度分析

• 空间复杂度：O(1)O(1)O(1)
• 时间复杂度：O(N)O(N)O(N)