Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594
给出一列数以及每个位置增/减1需要的cost,问最少多少cost可以让整列数变成一样的。因为最后相同的数必定在原数列最小值和最大值之间,而且总cost会是个U型曲线,所以二分结果找最小值
参考了Discussion -> https://leetcode.com/problems/minimum-cost-to-make-array-equal/solutions/3663660/binary-search-video-java-c-python/


 1 #2448
 2 #Runtime: 748 ms (Beats 42.86%)
 3 #Memory: 24.8 MB (Beats 71.43%)
 4 
 5 class Solution(object):
 6     def minCost(self, nums, cost):
 7         """
 8         :type nums: List[int]
 9         :type cost: List[int]
10         :rtype: int
11         """
12         def cal(m):
13             t = 0
14             for i in range(len(nums)):
15                 t += abs(nums[i] - m) * cost[i]
16             return t
17 
18         l, r = nums[0], nums[0]
19         for i in nums:
20             l = min(l, i)
21             r = max(r, i)
22         print(l)
23         print(r)
24         ans = 0
25         while l < r:
26             mid = (l + r) // 2
27             cost1 = cal(mid)
28             cost2 = cal(mid + 1)
29             if cost1 > cost2:
30                 l = mid + 1
31                 ans = cost2
32             else:
33                 r = mid
34                 ans = cost1
35         return ans

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