LeetCode 筆記 - 462. Minimum Moves to Equal Array Elements II

Posted on

題目在此 462. Minimum Moves to Equal Array Elements II

給定一個數列，每一步可以選定一格加 1 或減 1
請給出讓每個數字都相等的最小步驟

解題思維

如果沒寫過前一題可以先看一下
453. Minimum Moves to Equal Array Elements

剛看到這題的直覺是把所有數字都帶到平均值
但這個策略其實會增加移動成本

在這裡我們先有一個概念

現在有兩個數字 a 與 b 還有一個相遇點 meet point 寫為 m
只要 m 在 a 與 b 之間，那麼移動成本就會固定為 abs(a - b)
也就是說如果 m 在 a 與 b 之外的範圍，都會增加移動成本

好，具備這個概念之後，我們來看一個數列的情況

一個數列勢必存在 max value 與 min value
而移動至 max value 與 min value 之間的任一點，成本都是相同的

好，我們再近一步

將剛剛的 max value 與 min value 拿掉
就會出現新的 max value 2 與 min value 2
而移動至 max value 2 與 min value 2 之間的任一點，成本都是相同的

有感覺到了嗎？這問題的核心是在找到不會讓移動成本增加的點
而我們持續移除 max value 與 min value 的最終結果

就是 Median

所以找到中位數，然後計算移動成本就完成了 🥹

程式碼

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution(object):
    def minMoves2(self, nums):
        
        if (size := len(nums)) == 1:
            return 0
        
        nums.sort()
        median = size // 2
        
        result = 0
        for i in range(size):
            result += abs(nums[i] - nums[median])
            
        return result

也許你也會想看看