3
Effectively fetch the smallest element in a heap of Python
source link: https://donghao.org/2023/02/24/effectively-fetch-the-smallest-element-in-a-heap-of-python/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
Effectively fetch the smallest element in a heap of Python
To solve Leetcode #1675, I wrote the below code with the help of hints:
import sys import heapq class Solution: def minimumDeviation(self, nums: List[int]) -> int: n = len(nums) heapq.heapify(nums) _max = max(nums) ans = max(nums) - min(nums) while True: item = heapq.heappop(nums) if item % 2 == 1: heapq.heappush(nums, item * 2) _max = max(_max, item * 2) ans = min(ans, _max - heapq.nsmallest(1, nums)[0]) else: heapq.heappush(nums, item) break print("stage1:", nums) nums = [-item for item in nums] heapq.heapify(nums) _max = max(nums) while True: item = heapq.heappop(nums) if item % 2 == 0: heapq.heappush(nums, item // 2) _max = max(_max, item // 2) ans = min(ans, _max - heapq.nsmallest(1, nums)[0]) else: break return ans
Python
import sys
import heapq
class Solution:
def minimumDeviation(self, nums: List[int]) -> int:
n = len(nums)
heapq.heapify(nums)
_max = max(nums)
ans = max(nums) - min(nums)
while True:
item = heapq.heappop(nums)
if item % 2 == 1:
heapq.heappush(nums, item * 2)
_max = max(_max, item * 2)
ans = min(ans, _max - heapq.nsmallest(1, nums)[0])
else:
heapq.heappush(nums, item)
break
print("stage1:", nums)
nums = [-item for item in nums]
heapq.heapify(nums)
_max = max(nums)
while True:
item = heapq.heappop(nums)
if item % 2 == 0:
heapq.heappush(nums, item // 2)
_max = max(_max, item // 2)
ans = min(ans, _max - heapq.nsmallest(1, nums)[0])
else:
break
return ans
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK