Posted on 2022-12-04 14:41
Uriel 阅读(32)
评论(0) 编辑 收藏 引用 所属分类:
闲来无事重切Leet Code 、
大水题
给出一列数nums，求下标i，使得abs(mean(num[0]+...+sum[i]) - mean(num[i+1]+...+num[end]))最小，mean取整除值
预处理s[i]=sum(num[0]+...+sum[i])，然后扫一遍s数组，求均值差最小的下标，注意数列只有一个数的情况
1 #2256
2 #Runtime: 1974 ms
3 #Memory Usage: 24.9 MB
4
5 class Solution(object):
6 def minimumAverageDifference(self, nums):
7 """
8 :type nums: List[int]
9 :rtype: int
10 """
11 if len(nums) == 1:
12 return 0
13 s = [0] * (len(nums) + 1)
14 for i in range(1, len(nums) + 1):
15 s[i] = s[i - 1] + nums[i - 1]
16 min_diff = abs(s[1] - (s[len(nums)] - s[1]) // (len(nums) - 1))
17 ans = 0
18 for i in range(2, len(nums)):
19 if min_diff > abs(s[i] // i - (s[len(nums)] - s[i]) // (len(nums) - i)):
20 min_diff = abs(s[i] // i - (s[len(nums)] - s[i]) // (len(nums) - i))
21 ans = i - 1
22 if min_diff > abs(sum(nums) // len(nums)):
23 ans = len(nums) - 1
24 return ans