Medium

题目描述

给你一个长度为 n 的下标从 0 开始的整数数组 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 <= 10^5
  • 0 <= nums[i] <= 10^5

解题思路

解题思路

这道题的核心是计算每个下标处的平均差，需要高效地计算前缀和后缀的平均值。

思路分析

  1. 前缀和优化：使用前缀和数组来快速计算任意区间的和，避免重复计算。对于下标 i，前 i+1 个元素的和就是 prefixSum[i+1]。

  2. 后缀和计算：后 n-i-1 个元素的和可以通过总和减去前 i+1 个元素的和得到，即 totalSum - prefixSum[i+1]。

  3. 边界情况处理：当 i = n-1 时，后面没有元素，后缀平均值按题意视为 0。

  4. 整数除法：题目要求向下舍入，正好符合整数除法的特性。

算法步骤

  1. 计算数组总和和前缀和
  2. 遍历每个下标，计算对应的平均差
  3. 记录最小平均差及其对应的下标
  4. 返回最小下标

推荐解法：使用前缀和的一次遍历解法，时间复杂度 O(n)，空间复杂度 O(1)。

代码实现

class Solution {
public:
    int minimumAverageDifference(vector<int>& nums) {
        int n = nums.size();
        long long totalSum = 0;
        for (int num : nums) {
            totalSum += num;
        }
        
        long long prefixSum = 0;
        int minDiff = INT_MAX;
        int result = 0;
        
        for (int i = 0; i < n; i++) {
            prefixSum += nums[i];
            
            // 前缀平均值
            long long leftAvg = prefixSum / (i + 1);
            
            // 后缀平均值
            long long rightAvg = 0;
            if (i < n - 1) {
                rightAvg = (totalSum - prefixSum) / (n - i - 1);
            }
            
            int diff = abs(leftAvg - rightAvg);
            if (diff < minDiff) {
                minDiff = diff;
                result = i;
            }
        }
        
        return result;
    }
};

class Solution:
    def minimumAverageDifference(self, nums: List[int]) -> int:
        n = len(nums)
        total_sum = sum(nums)
        
        prefix_sum = 0
        min_diff = float('inf')
        result = 0
        
        for i in range(n):
            prefix_sum += nums[i]
            
            # 前缀平均值
            left_avg = prefix_sum // (i + 1)
            
            # 后缀平均值
            right_avg = 0
            if i < n - 1:
                right_avg = (total_sum - prefix_sum) // (n - i - 1)
            
            diff = abs(left_avg - right_avg)
            if diff < min_diff:
                min_diff = diff
                result = i
        
        return result

public class Solution {
    public int MinimumAverageDifference(int[] nums) {
        int n = nums.Length;
        long totalSum = 0;
        foreach (int num in nums) {
            totalSum += num;
        }
        
        long prefixSum = 0;
        int minDiff = int.MaxValue;
        int result = 0;
        
        for (int i = 0; i < n; i++) {
            prefixSum += nums[i];
            
            // 前缀平均值
            long leftAvg = prefixSum / (i + 1);
            
            // 后缀平均值
            long rightAvg = 0;
            if (i < n - 1) {
                rightAvg = (totalSum - prefixSum) / (n - i - 1);
            }
            
            int diff = (int)Math.Abs(leftAvg - rightAvg);
            if (diff < minDiff) {
                minDiff = diff;
                result = i;
            }
        }
        
        return result;
    }
}

var minimumAverageDifference = function(nums) {
    const n = nums.length;
    const totalSum = nums.reduce((sum, num) => sum + num, 0);
    
    let prefixSum = 0;
    let minDiff = Infinity;
    let result = 0;
    
    for (let i = 0; i < n; i++) {
        prefixSum += nums[i];
        
        // 前缀平均值
        const leftAvg = Math.floor(prefixSum / (i + 1));
        
        // 后缀平均值
        let rightAvg = 0;
        if (i < n - 1) {
            rightAvg = Math.floor((totalSum - prefixSum) / (n - i - 1));
        }
        
        const diff = Math.abs(leftAvg - rightAvg);
        if (diff < minDiff) {
            minDiff = diff;
            result = i;
        }
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度大小
时间复杂度O(n)
空间复杂度O(1)
  • 时间复杂度：O(n)，需要遍历数组一次计算总和，再遍历一次计算每个位置的平均差
  • 空间复杂度：O(1)，只使用了常数个额外变量

相关题目