Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594
给定一个数列costs,一共k次操作,每次从前candidates和后candidates个数里面选较小的一个,问k次取到的k个数只和
维护两个优先队列,一个存前candidates,一个存后candidates,注意每次pop之后要push后一个/前一个数


 1 #2462
 2 #Runtime: 1356 ms (Beats 44.93%)
 3 #Memory: 21.8 MB (Beats 68.12%)
 4 
 5 class Solution(object):
 6     def totalCost(self, costs, k, candidates):
 7         """
 8         :type costs: List[int]
 9         :type k: int
10         :type candidates: int
11         :rtype: int
12         """
13         left = costs[:candidates]
14         right = costs[max(candidates, len(costs) - candidates):]
15         heapify(left)
16         heapify(right)
17         ans = 0
18         i = candidates
19         j = len(costs) - candidates - 1
20         for _ in range(k):
21             if (not right) or (left and left[0] <= right[0]):
22                 ans += heappop(left)
23                 if i <= j:
24                     heappush(left, costs[i])
25                     i += 1
26             else:
27                 ans += heappop(right)
28                 if i <= j:
29                     heappush(right, costs[j])
30                     j -= 1
31         return ans

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