LeetCode 题解工作台
最小平均差
给你一个下标从 0 开始长度为 n 的整数数组 nums 。 下标 i 处的 平均差 指的是 nums 中 前 i + 1 个元素平均值和 后 n - i - 1 个元素平均值的 绝对差 。两个平均值都需要 向下取整 到最近的整数。 请你返回产生 最小平均差 的下标。如果有多个下标最小平均差相等，请…
2
题型
5
代码语言
3
相关题
当前训练重点
中等 · 前缀和
答案摘要
我们直接遍历数组 ，对于每个下标 ，维护前 $i + 1$ 个元素的和 和后 $n - i - 1$ 个元素的和 ，计算平均差的绝对值 ，如果 小于当前最小值 ，则更新答案 $ans = i$ 和最小值 $mi = t$。 遍历结束后，返回答案即可。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 前缀和 题型思路
题目描述
给你一个下标从 0 开始长度为 n 的整数数组 nums 。
下标 i 处的 平均差 指的是 nums 中 前 i + 1 个元素平均值和 后 n - i - 1 个元素平均值的 绝对差 。两个平均值都需要 向下取整 到最近的整数。
请你返回产生 最小平均差 的下标。如果有多个下标最小平均差相等，请你返回 最小 的一个下标。
注意：
- 两个数的 绝对差 是两者差的绝对值。
-
n个元素的平均值是n个元素之 和 除以（整数除法）n。 0个元素的平均值视为0。
示例 1：
输入：nums = [2,5,3,9,5,3] 输出：3 解释： - 下标 0 处的平均差为：|2 / 1 - (5 + 3 + 9 + 5 + 3) / 5| = |2 / 1 - 25 / 5| = |2 - 5| = 3 。 - 下标 1 处的平均差为：|(2 + 5) / 2 - (3 + 9 + 5 + 3) / 4| = |7 / 2 - 20 / 4| = |3 - 5| = 2 。 - 下标 2 处的平均差为：|(2 + 5 + 3) / 3 - (9 + 5 + 3) / 3| = |10 / 3 - 17 / 3| = |3 - 5| = 2 。 - 下标 3 处的平均差为：|(2 + 5 + 3 + 9) / 4 - (5 + 3) / 2| = |19 / 4 - 8 / 2| = |4 - 4| = 0 。 - 下标 4 处的平均差为：|(2 + 5 + 3 + 9 + 5) / 5 - 3 / 1| = |24 / 5 - 3 / 1| = |4 - 3| = 1 。 - 下标 5 处的平均差为：|(2 + 5 + 3 + 9 + 5 + 3) / 6 - 0| = |27 / 6 - 0| = |4 - 0| = 4 。 下标 3 处的平均差为最小平均差，所以返回 3 。
示例 2：
输入：nums = [0] 输出：0 解释： 唯一的下标是 0 ，所以我们返回 0 。 下标 0 处的平均差为：|0 / 1 - 0| = |0 - 0| = 0 。
提示：
1 <= nums.length <= 1050 <= nums[i] <= 105
解题思路
方法一：遍历
我们直接遍历数组 ，对于每个下标 ，维护前 个元素的和 和后 个元素的和 ，计算平均差的绝对值 ，如果 小于当前最小值 ，则更新答案 和最小值 。
遍历结束后，返回答案即可。
时间复杂度 ，其中 是数组 的长度。空间复杂度 。
class Solution:
def minimumAverageDifference(self, nums: List[int]) -> int:
pre, suf = 0, sum(nums)
n = len(nums)
ans, mi = 0, inf
for i, x in enumerate(nums):
pre += x
suf -= x
a = pre // (i + 1)
b = 0 if n - i - 1 == 0 else suf // (n - i - 1)
if (t := abs(a - b)) < mi:
ans = i
mi = t
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Can the candidate optimize the problem using prefix sums?
- question_mark
Is the candidate able to think about precalculation and its benefits?
- question_mark
Does the candidate consider edge cases, like arrays with a single element?
常见陷阱
外企场景- error
Not using prefix sums to optimize the calculation of averages.
- error
Recalculating sums repeatedly instead of leveraging precomputed values.
- error
Failing to handle arrays with a single element, which should return 0 immediately.
进阶变体
外企场景- arrow_right_alt
What if the array contains only one element?
- arrow_right_alt
How would the solution change if negative numbers are allowed in the array?
- arrow_right_alt
Can we optimize further for very large arrays?