最小平均差

标签: 数组 前缀和

难度: Medium

给你一个下标从 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 <= 105
  • 0 <= nums[i] <= 105

Submission

运行时间: 135 ms

内存: 25.0 MB

class Solution:
    def minimumAverageDifference(self, nums: List[int]) -> int:
        pre, suf, n = 0, 0, len(nums)
        suf = sum(nums)
        ans, min_diff = 0, inf

        for i in range(n-1):
            pre += nums[i]
            suf -= nums[i]
            diff = abs(pre // (i+1) - suf // (n-i-1))
            if diff < min_diff:
                min_diff = diff
                ans = i

        # 还有一个i = n-1的情况
        pre += nums[n-1]
        if pre // n < min_diff:
            ans = n-1
        return ans

Explain

此题解采用前缀和和后缀和的概念来计算每个下标处的平均差。使用两个变量pre和suf分别存储从数组开始到当前索引的元素之和（前缀和），以及当前索引后所有元素的和（后缀和）。通过逐步更新这两个和，我们可以有效地计算任意位置的平均差。循环遍历每个元素，更新前缀和与后缀和，并计算当前下标的平均差。如果计算得到的平均差小于之前的最小平均差，则更新最小平均差和对应的下标。最后，单独处理数组最后一个元素的情况，因为其后没有元素，后缀和为0。

时间复杂度: O(n)

空间复杂度: O(1)

# 该题解使用前缀和与后缀和的方法来计算最小平均差

class Solution:
    def minimumAverageDifference(self, nums: List[int]) -> int:
        pre, suf, n = 0, 0, len(nums)  # 初始化前缀和、后缀和以及数组长度
        suf = sum(nums)  # 计算整个数组的和作为初始后缀和
        ans, min_diff = 0, float('inf')  # 初始化答案和最小差的变量

        for i in range(n-1):
            pre += nums[i]  # 更新前缀和
            suf -= nums[i]  # 更新后缀和
            diff = abs(pre // (i+1) - suf // (n-i-1))  # 计算当前的平均差
            if diff < min_diff:
                min_diff = diff  # 更新找到的最小差
                ans = i  # 更新最小差对应的下标

        # 单独处理最后一个元素的情况
        pre += nums[n-1]  # 包括最后一个元素的前缀和
        if pre // n < min_diff:
            ans = n-1  # 如果最后一个元素的情况更优，则更新答案
        return ans  # 返回结果

Explore

在此题解中使用整数除法而不是浮点数除法是为了确保结果的稳定性和减少计算复杂度。整数除法（使用 // 运算符）会将结果直接向下取整到最近的整数，这样可以避免因为浮点数精度问题引起的不稳定性，特别是在比较差值时。此外，整数运算通常比浮点运算更快，有利于提高算法的执行效率。

当数组长度n为1时，算法中的循环会被跳过，因为它的范围是从0到n-2。因此，不会执行任何除以0的操作。在这种情况下，算法直接在循环外部处理最后一个元素，即只有一个元素的情况。这时，前缀和等于数组的唯一元素，后缀和为0，而整个数组的平均值也即是这个唯一元素的值，所以平均差为0。

单独处理最后一个元素的情况是因为在遍历过程中，最后一个元素的后缀和确实为0（因为没有更多的元素）。这种特殊情况需要单独处理，因为它只有前缀和而没有有效的后缀和。在前面的循环中，我们比较的是前缀和后缀的平均值，而对于最后一个元素，我们只需考虑前缀和（即整个数组的和）与整个数组长度的平均值。这是为了确保所有可能的平均差值都被考虑到，包括数组末尾的情况。

当数组中所有元素相等时，这种方法仍然有效。无论选择哪个元素作为分割点，前缀和和后缀和的平均值都将相同，因为所有元素都是相等的。这意味着计算出的平均差将是0。在这种情况下，最小平均差的位置可以是任何一个索引，但根据题解中的实现，如果所有平均差相同，会返回找到的第一个最小值的索引，即0。