2256. Minimum Average Difference
给你一个 Integer array nums，要你找出有最小 average difference 的 index
average difference 的定义为 abs(index前(含)的平均 - index后数字的平均)
其中算平均要使用整数除法
ex. nums = [2,5,3,9,5,3]
index = 0 的 average difference 为 | 2/1 - (5+3+9+5+3)/5 |
index = 1 的 average difference 为 | (2+5)/2 - (3+9+5+3)/4 |
如果有两个 index 的 average difference 一样则回传较小的 index
Example 1:
Input: nums = [2,5,3,9,5,3]
Output: 3
The average difference of index 3 = |(2+5+3+9)/4 - (5+3)/2| = |4-4| = 0
Example 2:
Input: nums = [0]
Output: 0
思路:
1.算区间总和可以先算出 prefix sum，之后能 O(1) 算出 nums[i~j] 的总和
prefix[0]=nums[0], prefix[1]=nums[0]+nums[1], prefix[2]=nums[0]+nums[1]+nums[2]
依此类推 之后如果要求 nums[i]+nums[i+1]+ ... + nums[j]
就可以直接算 prefix[j] - prefix[i-1]
2.这题的话因为是切成 nums[0:i+1] 和 nums[i+1:n]
左边的总和就是 prefix[i] 右边就是 prefix[n-1] - prefix[i]
之后就取平均然后相减取绝对值就好
3.
Python code:
class Solution:
def minimumAverageDifference(self, nums: List[int]) -> int:
n = len(nums)
prefix = list(accumulate(nums))
diff, idx = inf, 0
for i in range(n):
left = prefix[i] // (i+1)
right = 0 if i == n-1 else (prefix[n-1] - prefix[i]) // (n-1-i)
if abs(right - left) < diff:
diff = abs(right - left)
idx = i
return idx
又学到一招 accumulate