Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594
给出一列数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

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理