Problem#
題目給你一列正整數 N ，你可以對數列中的每個元素執行兩種操作:
- 如果
N[i]是偶數，可以除 2 - 如果
N[i]是奇數，可以乘 2
定義 deviation 是數列中的最大和最小之差 max(N) - min(N)
問你經過幾次操作後，最小的 deviation 是多少?
想法#
因為要求相差最小，所以我們希望數列中的最大值maxN越小越好；最小值minN越大越好。
由於題目沒有限制操作數，可以先將數列中的奇數都先乘2，這樣操作就只剩下偶數除二的情況。(此時數列中每個數字都是最大值)
接下來就只要看每次數列中最大的數字是不是偶數，如果是就除二，如果最大數字是奇數的話，就代表程式結束，接著就回傳當前最大和最小之差。
P.S. 維護最大值可以用 heap。
- 時間複雜度:
M = max(N[i])- $\mathcal{O}(NlogM\ \log{N})$
- 對於每個數
N[i]，最差要lg(M)次除法變成奇數，每次插入需要 $log(N)$
- 空間複雜度: $\mathcal{O}(N)$
AC Code#
賞析#
https://leetcode.com/problems/minimize-deviation-in-array/discuss/955262/C%2B%2B-intuitions-and-flip
TODO
心得#
一開始毫無頭緒QQ，看了題解後才知道如何解，要常寫 greedy 的題目ㄌ