What is the time complexity of the sorting approach for this problem?

The sorting approach has a time complexity of O(n log n) due to the sorting step.

How can I optimize the solution to avoid sorting?

You can optimize the solution by calculating the sum of the array, subtracting the minimum and maximum salaries, and then dividing by n-2.

What if the salary array has more than three elements?

The approach remains the same, regardless of the number of elements in the array, as long as there are at least three elements.

What should I do if the problem includes duplicate salaries?

You would need to modify the approach to handle duplicates, either by removing duplicates or adjusting how the minimum and maximum are determined.

How can I handle very large salary values efficiently?

Ensure the algorithm handles large numbers by focusing on O(n) solutions, such as sum-based calculations, to avoid issues with sorting overhead.

#1491

Easy

auto_awesome数组·排序

LeetCode 题解工作台

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

给你一个整数数组 salary ，数组里每个数都是唯一的，其中 salary[i] 是第 i 个员工的工资。请你返回去掉最低工资和最高工资以后，剩下员工工资的平均值。示例 1：输入： salary = [4000,3000,1000,2000] 输出： 2500.00000 解释：最低工…

数组排序

题目描述

给你一个整数数组 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
10^3 <= salary[i] <= 10^6
salary[i] 是唯一的。
与真实值误差在 10^-5 以内的结果都将视为正确答案。

lightbulb

解题思路

方法一：模拟

按题意模拟即可。

遍历数组，求出最大值和最小值，并且累加和，然后求出去掉最大值和最小值后的平均值。

时间复杂度 $O(n)$ 。其中 $n$ 为数组 salary 的长度。空间复杂度 $O(1)$ 。

1

2

3

4

5

class Solution:
    def average(self, salary: List[int]) -> float:
        s = sum(salary) - min(salary) - max(salary)
        return s / (len(salary) - 2)

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Look for the candidate's understanding of array manipulation and their ability to optimize solutions.
question_mark
Evaluate if the candidate can explain the trade-off between sorting and using sum subtraction.
question_mark
Assess if the candidate can handle edge cases like arrays with the minimum length of three.

warning

常见陷阱

外企场景

error
Forgetting to exclude both the minimum and maximum salaries before calculating the average.
error
Relying on sorting when the sum-based approach can offer better performance for larger arrays.
error
Not handling edge cases, such as arrays with exactly three elements or large salary ranges.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Modify the problem to include arrays with non-unique salaries and adjust the approach accordingly.
arrow_right_alt
Ask the candidate to optimize for time complexity by avoiding sorting.
arrow_right_alt
Introduce a scenario where the average needs to be calculated after excluding a different number of salary values.

help

常见问题

外企场景

继续练习

#1498 满足条件的子序列数目 #1481 不同整数的最少数目 #1502 判断能否形成等差数列