Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594
给出一列数,对于奇数,可以*2,对于偶数,可以/2,问执行任意多次操作之后,这列数的最大最小值之差最小是多少
参考了:https://leetcode.com/problems/minimize-deviation-in-array/solutions/3223578/priority-queue-video-java-c-python/
利用python的heapq


 1 #1675
 2 #Runtime: 5340 ms (Beats 100%)
 3 #Memory: 19.7 MB (Beats 100%)
 4 (Sorry, there are not enough accepted submissions to show data)
 5 
 6 class Solution(object):
 7     def minimumDeviation(self, nums):
 8         """
 9         :type nums: List[int]
10         :rtype: int
11         """
12         q = []
13         q_min = 2000000000
14         for i in nums:
15             if i % 2:
16                 i *= 2
17             heapq.heappush(q, -i)
18             q_min = min(q_min, i)
19 
20         ans = -q[0] - q_min
21         while q[0] % 2 == 0:
22             t = -heapq.heappop(q)
23             heapq.heappush(q, -(t // 2))
24             ans = min(ans, t - q_min)
25             q_min = min(q_min, t // 2)
26         return min(ans, -q[0] - q_min)

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