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 直接看他是不是奇數就知道是不是到頭了
推薦