Posted on 2022-12-04 14:41
Uriel 閱讀(51)
評論(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