1675. Minimize Deviation in Array
其实是昨天的题目
给你一个正整数 array nums，可以对任意元素做以下操作:
1.如果是偶数，除以二 2.如果是奇数，乘以二
操作不限次数，输出 max(nums) - min(nums) 最小可能是多少
Example 1:
Input: nums = [1,2,3,4]
Output: 1
Explanation: You can transform the array to [1,2,3,2], then to [2,2,3,2],
then the deviation will be 3 - 2 = 1.
Example 2:
Input: nums = [4,1,5,20,3]
Output: 3
Explanation: You can transform the array after two operations to [4,2,5,5,3],
then the deviation will be 5 - 2 = 3.
Example 3:
Input: nums = [2,10,8]
Output: 3
[2,10,8] -> [2,5,4] or [2,5,2]
思路:
1.每种元素都会有操作后的可能结果 比如说奇数3 -> [3,6] 偶数16 -> [1,2,4,8,16]
想办法去看每种可能结果当成最小值的情况下 当下的最佳解为何
检查所有这种最佳解 找出最小的就好
举例如果 nums = [4, 1, 5, 20, 3]
可能性: 4 1 5 20 3
2 2 10 10 6
1 5
假如我们想知道 1变成2 后的最佳结果 就要找出其他元素各自可能结果中比2大的最小值
也就是 4->2, 5不变, 20->5, 3不变
2.因为偶数可以除以二直到变成奇数为止 可能性最多会有31个
如果都暴力检查的话时间会是 O((n*32)^2) 显然会爆
这时候可以用 min heap 去加速比较 每次都检查最小的那个元素就好
那要怎么知道其他元素可能结果中的最小值
就可以一开始先把每个元素都除到最小然后丢进 heap 中
这样就能保证对最小的元素来说 其他 heap 中的元素都 1.比他大 2.不能再变小了
检查完最小的元素后就把他乘二加进 min heap 中
下一轮继续检查 heap top 直到 heap top 没有办法变化为止
这样每次在找最佳解时只需 O(1) 检查完乘2丢回 heap O(logn)
总共复杂度 O(32*nlogn)
上面省略了一点细节 像是丢进 heap 中要记住这个元素的最大值可以是多少
像是对16来说 他可以是 [1,2,4,8,16]
那一开始就丢 (1, 16) 进 heap 里
每次他变成 heap top 时会要乘二丢回去 等到他变成 (16, 16) 就可以直接结束了
因为这时候他已经没办法再变大了 其他元素的结果这时候都比他大 最小值会卡在16
所以后面就不用检查了
Python code:
class Solution:
def minimumDeviation(self, nums: List[int]) -> int:
heap = []
curmax = 0
for num in nums:
if num%2:
heapq.heappush(heap, (num, num*2))
curmax = max(curmax, num)
else:
minnum = num
while minnum%2 == 0:
minnum //= 2
heapq.heappush(heap, (minnum, num))
curmax = max(curmax, minnum)
res = inf
while heap:
top, bound = heapq.heappop(heap)
res = min(res, curmax - top)
if top == bound:
break
curmax = max(curmax, top*2)
heapq.heappush(heap, (top*2, bound))
return res
写完才想到用 max heap 应该更好写也更快
就不用维护每个数字的 bound 直接看他是不是奇数就知道是不是到头了
推荐