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