class Solution {
public:
int minimumAverageDifference(vector<int>& nums) {
}
};
2256. 最小平均差
给你一个下标从 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原站题解
java 解法, 执行用时: 5 ms, 内存消耗: 57.9 MB, 提交时间: 2023-09-06 23:39:45
class Solution {
public int minimumAverageDifference(int[] nums) {
long suf=0,pre=0;
for(int i=0;i<nums.length;i++){suf+=nums[i];}
int ans=-1;
long average=(long)1e12;
for(int i=0;i<nums.length;i++){
pre+=nums[i];
suf-=nums[i];
long d=i==nums.length-1?pre/nums.length:Math.abs(pre/(i+1)-suf/(nums.length-i-1));
if(d<average){
ans=i;
average=d;
}
}
return ans;
}
}
python3 解法, 执行用时: 220 ms, 内存消耗: 25.9 MB, 提交时间: 2023-09-06 23:39:24
class Solution:
def minimumAverageDifference(self, nums: List[int]) -> int:
n = len(nums)
prefix, total = 0, sum(nums)
min_agv, idx = float('inf'), -1
for i in range(n):
prefix += nums[i]
agv_prefix = prefix // (i + 1)
agv_surfix = 0 if i == n - 1 else (total - prefix) // (n - i - 1)
agv = abs(agv_prefix - agv_surfix)
if agv < min_agv:
min_agv = agv
idx = i
return idx
golang 解法, 执行用时: 88 ms, 内存消耗: 8.4 MB, 提交时间: 2023-09-06 23:38:49
func minimumAverageDifference(nums []int) (ans int) {
pre, suf, n := 0, 0, len(nums)
for _, v := range nums { suf += v } // 后缀和
minDiff := math.MaxInt64
for i, v := range nums[:n-1] {
pre += v // 前缀和
suf -= v // 后缀和
d := abs(pre/(i+1) - suf/(n-1-i))
if d < minDiff {
minDiff, ans = d, i
}
}
if (pre+nums[n-1])/n < minDiff { ans = n - 1 }
return ans
}
func abs(x int) int { if x < 0 { return -x }; return x }