2448. 讓陣列的值全部香等所需的最低花費
==========================
難度: Hard
類型: Matrix
CPP程式下載: 2448.cpp
==========================
覺得 minimum cost 類型的題目很生疏, 挑幾題來練習, 難度還是Hard
==========================
前情題要:
nums中第 i 個 elelment 要加一或減一所需的花費為 cost[i]
把所有 nums 中的成員都變成一樣的值, 求所需的最少花費
==========================
思考方式:
1. 最低的花費必定在 min_num 和 max_num 中間。
2. 有點像二次曲線找 minimum 的cost值, 有一個最低點, 然後兩邊的cost都越來越高。
3. 因為最後相同的值(target)必定是正整數, 所以可能有兩個target值都能得到minimum cost。
4. 用 binary search 比較快, 一次切西瓜挑中間值。
5. 每次 search 要算連續的兩個正整數, 中間值無條件捨去, 以及它的值加一。
6. 留意 boundary (邊界), 才能正確地找到最低花費, 停下來。
=======================
複雜度思考:
就 binary search 的模式。時間上就 N*log2(N)。空間上並沒有複製 vector, 也沒有做多餘的 memory table。
Time: O (N*log2(N))
Memory: O (1)
=======================
結果:
Accepted 48 / 48 testcases passed
Runtime: 0 ms, Beats: 100%
Memory: 42.20 MB, Beats: 78.24%
